这个题显然可以用树链剖分做。
然而线段树也能做。
每个点都对它的子树有贡献，所以先求一边 dfs序，然后直接在 dfs序 中搞 线段树 就行。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #define root 1, 1, n 4 #define ls now << 1, l, mid 5 #define rs now << 1 | 1, mid + 1, r 6 7 using namespace std; 8 9 const int MAXN = 100001; 10 int n, cnt, tim; 11 int head[MAXN], to[MAXN << 1], next[MAXN << 1], add[MAXN << 2], tid[MAXN], size[MAXN]; 12 13 inline void add_edge(int x, int y) 14 { 15 to[cnt] = y; 16 next[cnt] = head[x]; 17 head[x] = cnt++; 18 } 19 20 inline void dfs(int u) 21 { 22 int i, v; 23 tid[u] = ++tim; 24 size[u] = 1; 25 for(i = head[u]; i != -1; i = next[i]) 26 { 27 v = to[i]; 28 if(!size[v]) dfs(v), size[u] += size[v]; 29 } 30 } 31 32 inline void push_down(int now) 33 { 34 if(!add[now]) return; 35 add[now << 1] += add[now]; 36 add[now << 1 | 1] += add[now]; 37 add[now] = 0; 38 } 39 40 inline int query(int x, int now, int l, int r) 41 { 42 if(l == r) return add[now]; 43 push_down(now); 44 int mid = (l + r) >> 1; 45 if(x <= mid) return query(x, ls); 46 else return query(x, rs); 47 } 48 49 inline void update(int x, int y, int now, int l, int r) 50 { 51 if(x <= l && r <= y) 52 { 53 add[now]++; 54 return; 55 } 56 if(l > y || r < x) return; 57 push_down(now); 58 int mid = (l + r) >> 1; 59 update(x, y, ls); 60 update(x, y, rs); 61 } 62 63 int main() 64 { 65 int i, x, y; 66 scanf("%d", &n); 67 memset(head, -1, sizeof(head)); 68 for(i = 1; i < n; i++) 69 { 70 scanf("%d %d", &x, &y); 71 add_edge(x, y); 72 add_edge(y, x); 73 } 74 dfs(1); 75 for(i = 1; i <= n; i++) 76 { 77 scanf("%d", &x); 78 printf("%d ", query(tid[x], root)); 79 update(tid[x], tid[x] + size[x] - 1, root); 80 } 81 return 0; 82 }