并查集+01背包（滚动数组）

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]);
    }
}