Jumping Monkey

电玩女神 2022-09-15 12:22 154阅读 0赞

[Problem - 7136 (hdu.edu.cn)][Problem - 7136 _hdu.edu.cn]

# Jumping Monkey #

***\*Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)  
Total Submission(s): 644 Accepted Submission(s): 304  
\****

Problem Description

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\], 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≤105), representing the number of nodes.

Each of the following n−1 lines contains two integers u,v (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≤109), representing the weight of each node.

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

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$, he can reach at most $4$ nodes in the order of $1 \to 3 \to 2 \to 4$.

Source

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55m96Iq36aao_size_20_color_FFFFFF_t_70_g_se_x_16]

Recommend

IceyWang | We have carefully selected several similar problems for you: [7137][] [7136][Problem - 7136 _hdu.edu.cn] [7135][] [7134][] [7133][]

#include<algorithm>
    #include<iostream>
    #include<vector>
    #include<set>
    using namespace std;
    const int N = 1e6 + 10;
    vector<int> e[N],g[N];
    pair<int, int> w[N];
    int n,vis[N],ans[N];
    int p[N];
    int find(int x) {
    	if (x == p[x])return p[x];
    	else return p[x] = find(p[x]);
    }
    void dfs(int u,int fa,int dep)
    {
    	ans[u] = dep;
    	for (auto v : g[u]) {
    		if (v == fa)continue;
    		dfs(v, u, dep + 1);
    	}
    }
    void solve()
    {
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i++)e[i].clear(), g[i].clear(),vis[i]=0,ans[i]=0,p[i]=i;
    
    	for (int i = 1; i < n; i++) {
    		int a, b;
    		scanf("%d%d", &a, &b);
    		e[a].push_back(b);
    		e[b].push_back(a);
    	}
    	for (int i = 1; i <= n; i++)scanf("%d", &w[i].first), w[i].second = i;
    	sort(w + 1, w + 1 + n);
    	
    	for (int i = 1; i <= n; i++) {
    		
    		int u = w[i].second;
    		set<int> st;
    		for (auto v : e[u])
    			if (vis[v])
    			{
    				int fu = u, fv = find(v);
    				st.insert(fv);
    			}
    		for (auto it : st) {
    			p[it] = u;
    			g[u].push_back(it);
    		}
    		vis[u] = 1;
    
    	}
    	dfs(w[n].second, 0, 1);
    	for (int i = 1; i <= n; i++)printf("%d\n", ans[i]);
    }
    int main()
    {
    	int T; scanf("%d", &T);
    	while (T--)solve();
    	return 0;
    }

[Problem - 7136 _hdu.edu.cn]: https://acm.hdu.edu.cn/showproblem.php?pid=7136
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55m96Iq36aao_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/20e7cdfa31a14f2c8098313d4683ea49.png
[7137]: https://acm.hdu.edu.cn/showproblem.php?pid=7137
[7135]: https://acm.hdu.edu.cn/showproblem.php?pid=7135
[7134]: https://acm.hdu.edu.cn/showproblem.php?pid=7134
[7133]: https://acm.hdu.edu.cn/showproblem.php?pid=7133