题目背景
从前森林里有一棵很大的mjt树，树上有很多小动物。
题目描述
mjt树上有 n 个房间，第 i 个房间住着 ai 只第bi 种小动物。
这n个房间用n-1条路连接起来，其中房间1位mjt树的根。
现在每个房间x的小动物想知道，以房间x为根的mjt树中有多少只它们的同类.
输入输出格式
输入格式：
第一行一个整数n，表示房间数
接下来n行，每行两个整数ai，bi
再之后n-1，每行两个整数x、y，表示x和y之间有一条路径
输出格式：
一行n个数，第i个数表示以房间i为根的mjt树中bi种小动物有多少只，两个数之间用空格隔开
输入输出样例
输入样例#1：
5
2 1
3 1
4 2
5 1
6 2
1 2
1 3
3 4
3 5
输出样例#1：
10 3 10 5 6
说明
bi<=n<=100000,ai<=1000
by xjjppm.
我也不知道我是怎么想出来的这么鬼畜的做法
对于每个颜色记录出该颜色上一次出现的位置
然后拓扑排序。。
各位都是一遍dfs 太强了orz。
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[ << ], *p1 = buf, *p2 = buf;
//#define int long long
using namespace std;
const int MAXN = * 1e5 + ;
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
struct Edge {
int u, v, nxt;
}E[MAXN];
int head[MAXN], num = ;
inline void AddEdge(int x, int y) {
E[num] = (Edge){x, y, head[x]};
head[x] = num++;
}
int N, a[MAXN], b[MAXN], ans[MAXN], inder[MAXN], pre[MAXN];
vector<int>v[MAXN];
void dfs(int x, int fa) {
for(int i = head[x]; i != -; i = E[i].nxt) {
if(E[i].v == fa) continue;
if(pre[b[E[i].v]])
v[E[i].v].push_back(pre[b[E[i].v]]), inder[pre[b[E[i].v]]]++;
int gg = pre[b[E[i].v]];
pre[b[E[i].v]] = E[i].v;
dfs(E[i].v, x);
pre[b[E[i].v]] = gg;
} }
void Topsort() {
queue<int>q;
for(int i = ; i <= N; i++)
if(!inder[i]) q.push(i);
while(q.size() != ) {
int p = q.front(); q.pop();
for(int i = ; i < v[p].size(); i++) {
a[v[p][i]] += a[p];
inder[v[p][i]]--;
if(!inder[v[p][i]]) q.push(v[p][i]);
}
}
}
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
memset(head, -, sizeof(head));
N = read();
for(int i = ; i <= N; i++) a[i] = read(), b[i] = read();
for(int i = ; i <= N - ; i++) {
int x = read(), y = read();
AddEdge(x, y); AddEdge(y, x);
}
pre[b[]] = ;
dfs(, );
Topsort();
for(int i = ; i <= N; i++)
printf("%lld ", a[i]);
return ;
}