[HDU 7136] Jumping Monkey | 并查集 | 逆向思维

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 747 Accepted Submission(s): 360

There is a tree with n nodes and n−1 edges that make all nodes connected. Each node i has a distinct weight ai. A monkey is jumping on the tree. In one jump, the monkey can jump from node u to node v if and only if av is the greatest of all nodes on the shortest path from node u to node v. The monkey will stop jumping once no more nodes can be reached.

For each integer k ∈ [ 1 , n ] k∈[1,n] k∈[1,n], calculate the maximum number of nodes the monkey can reach if he starts from node k.

Input
The first line of the input contains an integer T (1≤T≤104), representing the number of test cases.

The first line of each test case contains an integer n (1≤n≤10⁵), representing the number of nodes.

Each of the following n−1 lines contains two integers u,v ( 1 ≤ u , v ≤ n ) (1≤u,v≤n) (1≤u,v≤n), representing an edge connecting node u and node v. It is guaranteed that the input will form a tree.

The next line contains n distinct integers a1,a2,…,an (1≤ai≤10⁹), representing the weight of each node.

It is guaranteed that the sum of n over all test cases does not exceed 8×10⁵.

Output
For each test case, output n lines. The k-th line contains an integer representing the answer when the monkey starts from node k.

Sample Input

2
3
1 2
2 3
1 2 3
5
1 2
1 3
2 4
2 5
1 4 2 5 3

Sample Output

3
2
1
4
2
3
1
3

Hint

For the second case of the sample, if the monkey starts from node 1 1 1, he can reach at most 4 4 4 nodes in the order of 1 → 3 → 2 → 4 1 to 3 to 2 to 4 1→3→2→4.

#define Clear(x,val) memset(x,val,sizeof x)
vector vet[maxn];
vector after[maxn];/// save the ans tree
int fa[maxn], n;
bool vis[maxn];
void init() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i, vis[i] = 0;
		vet[i].clear();
		after[i].clear();
	}
}
int find(int x) {
	if (x == fa[x]) return x;
	else return fa[x] = find(fa[x]);
}
typedef pair PII;
PII a[maxn];
int ans[maxn];
void getDepth(int cur, int faNode, int depth) {
	ans[cur] = depth;
	for (int to : after[cur]) {
		if (to == faNode) continue;
		getDepth(to, cur, depth + 1);
	}
}
int main() {
	int _ = read;
	while (_--) {
		n = read;
		init();
		for (int i = 1; i < n; i++) {
			int u = read, v = read;
			vet[u].push_back(v);
			vet[v].push_back(u);
		}
		for (int i = 1; i <= n; i++) {
			a[i].first = read;
			a[i].second = i;
		}
		sort(a + 1, a + 1 + n);
		//puts("OK");
		for (int i = 1; i <= n; i++) {
			int u = a[i].second;/// the second
			vector t;
			for (int v : vet[u]) {
				if (vis[v]) {
					int fav = find(v);
					t.push_back(fav);
				}
			}
			for (int v : t) {
				fa[v] = u;///trans the father of node_v
				after[u].push_back(v);
			}
			vis[u] = 1;
		}
		getDepth(a[n].second, 0, 1);
		for (int i = 1; i <= n; i++) {
			printf("%dn", ans[i]);
		}
	}
	return 0;
}