오일러 투어 테크닉 (Euler Tour Technique)

# Euler Tour + 서브트리 합
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
​
N, Q = map(int, input().split())
val = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  a -= 1; b -= 1
  adj[a].append(b); adj[b].append(a)
​
tin = [0] * N
tout = [0] * N
timer = [0]
​
def dfs(u, p):
  timer[0] += 1
  tin[u] = timer[0]
  for v in adj[u]:
      if v != p:
          dfs(v, u)
  tout[u] = timer[0]
​
dfs(0, -1)
​
# 서브트리 합 = val[tin[u]..tout[u]] 구간 합
# prefix sum 으로 구현
prefix = [0] * (2 * N + 5)
for i in range(N):
  prefix[tin[i]] += val[i]
for i in range(1, 2 * N + 1):
  prefix[i] += prefix[i - 1]
​
out = []
for _ in range(Q):
  u = int(input()) - 1
  out.append(str(prefix[tout[u]] - prefix[tin[u] - 1]))
print("\n".join(out))

// Euler Tour + 서브트리 합
import java.util.*;
import java.io.*;
public class Main {
  static List<Integer>[] adj;
  static int[] tin, tout, val;
  static long[] prefix;
  static int timer = 0, N;
​
  static void dfs(int u, int p) {
      tin[u] = ++timer;
      for (int v : adj[u]) if (v != p) dfs(v, u);
      tout[u] = timer;
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      int Q = Integer.parseInt(st.nextToken());
      val = new int[N];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < N; i++) val[i] = Integer.parseInt(st.nextToken());
      adj = new ArrayList[N];
      for (int i = 0; i < N; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < N - 1; i++) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken()) - 1;
          int b = Integer.parseInt(st.nextToken()) - 1;
          adj[a].add(b); adj[b].add(a);
      }
      tin = new int[N];
      tout = new int[N];
      dfs(0, -1);
      prefix = new long[2 * N + 5];
      for (int i = 0; i < N; i++) prefix[tin[i]] += val[i];
      for (int i = 1; i <= 2 * N; i++) prefix[i] += prefix[i - 1];
      StringBuilder sb = new StringBuilder();
      while (Q-- > 0) {
          int u = Integer.parseInt(br.readLine()) - 1;
          sb.append(prefix[tout[u]] - prefix[tin[u] - 1]).append('\n');
      }
      System.out.print(sb);
  }
}