其实根本不需要找根节点

上司去了下属不去

和下属去了上司一定不去

没有区别

加上代码

#include<bits/stdc++.h>
using namespace std;
const int slen=6010*2;
int happy[slen];
int node[slen],pnext[slen],edge[slen],num;
//是否已经作为父结点了 
bool st[slen];
int dp[slen][2];
void add(int fa,int ch)
{
//储存职员和上司之间的关系
edge[++num]=ch;
pnext[num]=node[fa];
node[fa]=num;
}
void dfs(int u,int ba)
{
dp[u][1]=happy[u];
for(int i=node[u];i!=-1;i=pnext[i])
{
  int j=edge[i];
  if(j==ba) continue;
  dfs(j,u);//根结点递归在它的每个子结点
  dp[u][0]+=max(dp[j][0],dp[j][1]);
  dp[u][1]+=dp[j][0];
}
}
int main()
{
int n,i,a,b;
cin>>n;
for(i=0;i<slen;++i)
  node[i]=-1;
for(i=1;i<=n;i++) cin>>happy[i];
for(i=1;i<n;i++)
{
  cin>>a>>b;
  st[a]=true;
  add(b,a),add(a,b); 
}
int root=1;
//while(st[root])root++;//寻找没有上司的节点作为根结点
dfs(root,-1);//递归调用
printf("%d",max(dp[root][0],dp[root][1]));//输出两种情况的最大值
return 0;
}