题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7136

这道题当时预赛赛场死活没想出来一种好的解法，今天看了下题解补上了

官方题解中所说的办法，前半段我想到了，就是说每次去找出权值最大的点，它会阻断其子树之间的移动，并且它的所有子节点都肯定能到达它，然后把树拆成森林继续上述操作，但这个真的很难写。。。我是没写出来

然后关键一步是下面的：将这棵树重构，使得权值更大的点在上面，且从根节点到任意子节点拎出来的任意一条链从上到下都是递减的，最后能保证的性质是，任何一个节点其子节点都可在原来的树上到达它。

先放个代码

#include <bits/stdc++.h>
using namespace std;
vector<int>G[150000];
pair<int,int> node[150000];
bool vis[150000];
int ans[150000],fa[150000],nxt[150000];
int find(int x){
	return (x==fa[x])?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(x);nxt[x]=y;
	fa[x]=y;
}
int dfs(int now){
//	cout<<now<<endl;
	if(ans[now]) return ans[now];
	if(nxt[now]==0) return ans[now]=1;
	return ans[now]=dfs(nxt[now])+1;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			G[i].clear();
			ans[i]=0;
			vis[i]=0,fa[i]=i,nxt[i]=0;
		}
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v),G[v].push_back(u);
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&node[i].first);node[i].second=i;
		}
		sort(node+1,node+1+n);
		for(int i=n;i>=1;i--){
			int u=node[i].second;
			vis[u]=1;
			for(auto v:G[u]){
				if(!vis[v]) continue;
				vis[v]=1;
				merge(v,u);
			}
		}
		for(int i=1;i<=n;i++) dfs(i);
		for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	}
	return 0;
}

大致再重新说一下经过一番思考之后对这道题题解的看法，按照刚开始的方案，在删除了一棵树的根节点后，很不容易去找到每一个森林的最大权值点，而用以上方式重构出来的树，每个森林的最大权值点会直接的连接在当前根节点上

很巧妙的做法，好题+1