经商

题解：并查集+dp
十分基础的一个并查集的题目（只考了并查集的基本操作），我们找出与小d所连的所有序号，在这个集合里进行01背包操作即可。
这里并查集用一下路径压缩的写法吧，不仅写法简单明了，而且还快速。
注意的是：不要忘记每次清空数组。

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e4+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int f[maxn],a[maxn],b[maxn];
int dp[maxn];
int ifind(int x){
    if(f[x]==x) return x;
    return f[x]=ifind(f[x]);
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=0;i<maxn;i++) f[i]=i;
        for(int i=2;i<=n;i++){
            scanf("%d%d",&a[i],&b[i]);
        }
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            int dx=ifind(x);
            int dy=ifind(y);
            if(dx!=dy){
                f[dx]=dy;
            }
        }
        memset(dp,0,sizeof(dp));
        for(int i=2;i<=n;i++){
            if(ifind(i)==ifind(1)){
                for(int j=k;j>=a[i];j--){
                    dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
                }
            }
        }
        printf("%d\n",dp[k]);
    }
    return 0;
}