题目链接:https://ac.nowcoder.com/acm/problem/14348

分析：读完题目我们可以发现，题目中频繁的涉及一个人和另一个人之间的关系，并且关系之间具有传递性，我们把所有认识的人看成一个集合，不难想到用并查集来维护所有相互认识的人构成的集合

  int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
  //别忘了初始化
  for(int i=1;i<=n;i++)
        p[i]=i;
  while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int pa=find(x);
        int pb=find(y);
        if(pa!=pb) p[pa]=pb;
    }

接着分析，可以发现小d有一定的精力值c，并且和第i个人认识要花费ai的精力值，获得bi的利益值，求最大的利益值，很明显这是一个01背包问题，在小d认识的集合中做01背包,最后f[c]就是答案

  01背包
  memset(f,0,sizeof f);
  //因为有多组测试数据，所以不要忘了每次初始化dp数组
    for(int i=2;i<=n;i++)
        if(find(1)==find(i)){
            for(int j=c;j>=w[i];j--)
                f[j]=max(f[j],f[j-w[i]]+g[i]);
        }
    printf("%d\n",f[c]);

Acode:

 #include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=1e5+5;
int t;
int n,m,c;
int p[N];
int w[N],g[N];
int f[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
void solve(){
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=2;i<=n;i++)
        scanf("%d%d",&w[i],&g[i]);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int pa=find(x);
        int pb=find(y);
        if(pa!=pb) p[pa]=pb;
    }
    memset(f,0,sizeof f);
    for(int i=2;i<=n;i++)
        if(find(1)==find(i)){
            for(int j=c;j>=w[i];j--)
                f[j]=max(f[j],f[j-w[i]]+g[i]);
        }
    printf("%d\n",f[c]);
}
signed main(){
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}