链接：https://ac.nowcoder.com/acm/problem/14545
来源：牛客网

题目描述
小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。

小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。

小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。

小d想知道，他在精力范围内，能够获得的利益值到底是多少。

设定小d自己的编号为1.并且对应一个人的交际次数限定为1.

输入描述:
本题包含多组输入，第一行输入一个数t，表示测试数据的组数
每组数据的第一行输入三个数，N,M，C，表示这个人际关系网一共有多少个人，关系网的关系数，以及小d的精力值
接下来N-1行，每行两个数ai，bi。这里第i行表示和编号为i+1的人认识需要花费ai的精力，能够获得的利益值为bi。
再接下来M行，每行两个数x，y，表示编号为x的人能够和编号为y的人接触
t<=50
2<=N<=10000
1<=M<=10*N
1<=ai，bi<=10
1<=C<=500
1<=x,y<=N
输出描述:
输出包含一行，表示小d能够获得的最大利益值
示例1
输入
复制
1
5 3 7
5 10
3 2
4 3
1 100
1 2
2 3
1 4
输出
复制
10

#include<stdio.h>
#include<string.h>
int f[10010];
int dp[10010];
int w[10010],v[10010];
int find(int x){
   if(x==f[x]) return x;
   else {///路径压缩
     int t = find(f[x]);
     f[x] = t;
     return t;
   }
}
void merge(int x,int y){
    int fa,fb;
    fa = find(x);
    fb = find(y);
    if(fa!=fb)
        f[fb] = fa;
}
int main(){
    int t;
    int n,m,c;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&c);
        for(int i=1;i<=n;i++) f[i] = i;
        for(int i=2;i<=n;i++){
            scanf("%d%d",&w[i],&v[i]);
        }
        int a,b;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            merge(a,b);
        }
        memset(dp,0,sizeof(dp));
        for(int i=2;i<=n;i++)
            for(int j=c;j>=w[i];j--)
                if(find(i)==find(1)&&dp[j]<(dp[j-w[i]]+v[i]))
                  dp[j] = dp[j-w[i]]+v[i];

        printf("%d\n",dp[c]);
    }
}