思路：先并查集求出和1号在同一个连通块的的人，然后进行01背包。
const int N = 1e5 + 5; int a[N], b[N], dp[N]; int fa[N]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } int t; int main() { //freopen("in.txt", "r", stdin); cin >> t; while (t--) { int n, m, c; scanf("%d%d%d", &n, &m, &c); f(i, 1, N)fa[i] = i; f(i, 1, n-1) scanf("%d%d", &a[i+1], &b[i+1]); int x, y; f(i, 1, m) { scanf("%d%d", &x, &y); int f1 = find(x), f2 = find(y); if (f1 < f2)fa[f2] = f1; else fa[f1] = f2; } memset(dp, 0, sizeof dp); f(i, 2, n) { if (find(i) == 1) { for (ll j = c;j >= a[i];--j) { dp[j] = max(dp[j], dp[j - a[i]] + b[i]); } } } cout << dp[c] << endl; } return 0; }