牛客经商（并查集+01背包）

小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
5 3 7
5 10
3 2
4 3
1 100
1 2
2 3
1 4

输出
10

PS：
刚开始并没有想到这是一个并查集+01背包，我就以为是一个简单的并查集然后贪心就完事了，但是当时纠结的是，两边都可以贪心（精力和利益值），当时没多想随便找一个贪心然后代码过了样例，交上去的时候却wa了，这时候就开始认真分析问题了。
求解最大值有两种方式，一个是二分，一个是动态规划，这里毫无疑问是动态规划，所有的条件里面选一个最大的，这里我们用滚动数组极大的简化了代码，也使程序看起来通俗易懂，具体注释请看代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int pre[maxn], a[maxn], b[maxn], dp[maxn];
int find(int x)
{
   
    if (x != pre[x])
        pre[x] = find(pre[x]);
    return pre[x];
}
int main()
{
   
    int t, n, m, c, ans, cnt;
    scanf("%d", &t);
    while (t--)
    {
   
        ans = 0, cnt = 0;
        scanf("%d%d%d", &n, &m, &c);
        for (int i = 1; i <= n; ++i)
            pre[i] = i;
        for (int i = 2; i <= n; ++i)
            scanf("%d%d", &a[i], &b[i]);
        for (int j = 1; j <= m; ++j)
        {
   
            int x, y;
            scanf("%d%d", &x, &y);
            pre[find(x)] = find(y); //合并操作
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 2; i <= n; ++i)
            if (find(i) == find(1)) //在满足条件的情况下才去dp
            {
   
                for (int j = c; j >= a[i]; --j)
                    dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
            }
        printf("%d\n", dp[c]);
    }
}