hdu5923 Prediction

jxt的思路 先膜一发
先处理 T这棵树上每个点到祖先这条链的点所生成的并查集
每个点的并查集都得分开来存
这个dfs做就好了
最后询问的时候 将k 个点的并查集合并就是这个询问的连通图
易得答案

#include<bits/stdc++.h>

using namespace std;

#define sz(X)  ((int)X.size())

int n,m,q;

vector<int> mp[10005];

int f[10005][505];

int find(int x, int ty){return x==f[ty][x]?x:(f[ty][x]=find(f[ty][x], ty));}

int E[10005][2];

int so[505];

int cn[505];

void dfs(int x, int pre) {

    for(int i = 1; i <= n; ++i) f[x][i] = f[pre][i];

    int fx= find(E[x][0],x); int fy = find(E[x][1],x);

    if(fx != fy) f[x][fx] = fy;

    for(int i = 0; i < sz(mp[x]); ++i) {

        int y = mp[x][i];

        dfs(y,x);

    }

}

int main(){

    int _; scanf("%d",&_);

    for(int cas=1;cas<=_;cas++) {

        memset(cn,0,sizeof(cn));

        scanf("%d %d",&n,&m);

        for(int i = 1; i <= n; ++i) f[1][i] = i;

        for(int i = 1; i <= m; ++i) mp[i].clear();

        for(int i = 2; i <= m; ++i) {

            int a; scanf("%d",&a);

            mp[a].push_back(i);

        }

        for(int i = 1; i <= m; ++i) {

            scanf("%d %d",&E[i][0],&E[i][1]);

        }

        dfs(1,1);

        scanf("%d",&q);

        printf("Case #%d:\n",cas);

        for(int i = 1; i <= q; ++i) {

            for(int j = 1; j <= n; ++j) f[0][j] = j;

            int k; scanf("%d",&k);

            for(int j = 0; j < k; ++j) {

                int a; scanf("%d",&a);

                for(int l = 1; l <= n; l++) {

                    int t1 = find(l,a);

                    if(t1 != l) {

                        int x = find(t1,0); int y = find(l,0);

                        if(x != y) f[0][x] = y;

                    }

                }

            }

            int ans = 0;

            for(int j = 1; j <= n; ++j) {

                int x = find(j,0);

                if(cn[x] < i) ans ++;

                cn[x] = i;

            }

            printf("%d\n",ans);

        }

    }

    return 0;

}