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≤1e4), representing the number of test cases.
The first line of each test case contains an integer n (1≤n≤1e5), 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≤1e9), representing the weight of each node.
It is guaranteed that the sum of n over all test cases does not exceed 8×1e5.
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
题意：
给你一棵树，然后猴子在树上跳，猴子能从 i 点跳到 j 点当且仅当从 i 到 j 的路径中 j 的权重最大，现在让你求出从每一个点出发所能经过的最多节点数
题解：
就是并查集，这个集合内的点可以说是随便跳的，就是在这个集合里的答案就是他是第几大数，然后做法就是按权值从小到大排序，然后枚举节点u，u就作为与u相连的联通块的根，这是为什么呢，是因为现在的联通块里面的节点的权值是都比 u 的权值小的，然后咱们一会儿就是从权值最大的点进行dfs的，所以咱们需要连一条单向边，表示联通块里的所有元素都能到这个点，而且跳到这个点之后还可以跳到连向 u 的点，所以说这类似于反向建边了，然后就反向建边反向递推就出来了，可能比较难想（对于我这种菜鸡来说）哈哈哈，下面请看代码吧
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
typedef long long LL;
vector<int> G[N],NG[N];
int pa[N];
int find(int x){
if(x != pa[x]) pa[x] = find(pa[x]);
return pa[x];
}
PII a[N];
bool st[N];
int ans[N];
void dfs(int u,int fa){
for(auto j : NG[u]){
if(j == fa) continue;
ans[j] = ans[u] + 1;
dfs(j,u);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) G[i].clear() , NG[i].clear() , pa[i] = i , st[i] = false;
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i].first);
a[i].second = i;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
int u = a[i].second;
for(auto j : G[u]){
if(!st[j]) continue;
int v = find(j);
pa[v] = u;
NG[u].push_back(v);
}
st[u] = true;
}
ans[a[n].second] = 1;
dfs(a[n].second,0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
return 0;
}
|