题目链接:传送门

Description

分别给你一个有根树还有一个图，有根树得每个节点代表图的一条边。每次询问给你一个集合，把集合里所有的点以及所有点的祖先节点代表得边连起来。问连接后的图中连通块的个数

Solution

我们考虑每个点建一个并查集，在从根dfs时维护从它到根所有点都选中时原图的状况，查询时暴力合并这些并查集即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 500 + 10, Maxm = 10000 + 10;

int fa[Maxm][Maxn];
int e, Begin[Maxm], Next[Maxm * 2], To[Maxm * 2];
int N, M, Q;

struct node
{
    int x, y;
}A[Maxm];

inline void Init ()
{
    e = 0;
    memset(Begin, 0, sizeof Begin);
    memset(fa, 0, sizeof fa);
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

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

inline void Link (int *f, int x, int y)
{
    int fx = find(f, x);
    int fy = find(f, y);
    if (fx == fy) return ;
    f[fy] = fx;
}

inline void dfs (int x, int f)
{
    for (int i = 1; i <= N; ++i) fa[x][i] = fa[f][i];
    Link (fa[x], A[x].x, A[x].y);
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == f) continue;
        dfs(y, x);
    }
}

int Vis[Maxm];
int tot;

inline void Solve()
{
    scanf("%d%d", &N, &M);
    for (int i = 2; i <= M; ++i)
    {
        int x;
        scanf("%d", &x);
        add_edge (x, i);
        add_edge (i, x);
    }
    for (int i = 1; i <= M; ++i)
        scanf("%d%d", &A[i].x, &A[i].y);
    for (int i = 1 ; i <= N; ++i) fa[0][i] = i;
    dfs(1, 0);
    scanf("%d", &Q);
    printf("Case #%d:\n", ++tot);
    while (Q--)
    {
        int x;
        scanf("%d", &x);
        for (int i = 1; i <= N; ++i) Vis[i] = i;
        while (x--)
        {
            int k;
            scanf("%d", &k);
            for (int i = 1; i <= N; ++i)
                Link(Vis, i, find(fa[k], i));
        }
        int Ans = 0;
        for (int i = 1; i <= N; ++i) if (Vis[i] == i) ++Ans;
        cout<<Ans<<endl;
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while (T--)
    {
        Init();
        Solve();
    }
    return 0;
}