A. 树

  • 并查集 + dfs + 离线
    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
    const int N=1e5+2;
    char s[N][2];
    int x,y,a[N],b[N],fa[N],f[N];
    int n,m,cnt,hd[N],to[N],nxt[N],ans[N];
    void add(int x,int y)
    {
    	to[++cnt]=y;
    	nxt[cnt]=hd[x];
    	hd[x]=cnt;
    }
    void dfs(int x,int fat)
    {
    	if(b[x])f[x]=x;
    	else f[x]=f[fat];
    	fa[x]=fat;
    	for(int i=hd[x];i;i=nxt[i])
    		dfs(to[i],x);
    }
    int find(int x)
    {
    	return x==f[x]?x:f[x]=find(f[x]);
    }
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<n;++i)
    		scanf("%d%d",&x,&y),add(x,y);
    	for(int i=1;i<=m;++i)
    	{
    		scanf("%s%d",s[i],&a[i]);
    		if(*s[i]=='C')++b[a[i]];
    	}
    	++b[1];dfs(1,0);cnt=0;
    	for(int i=m;i;--i)
    	{
    		if(*s[i]=='Q')ans[++cnt]=find(a[i]);
    		else if(!(--b[a[i]]))f[a[i]]=f[fa[a[i]]];
    	}
    	for(int i=cnt;i;--i)
    		printf("%d\n",ans[i]);
    }

B. 集合操作

  • 启发式合并
    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
    const int N = 2e5+100;
    int n,m,f[N],siz[N],tag[N];
    vector<int> a[N];
    int v[N];
    inline int find(int x)
    {
    	if(f[x]!=x)return f[x]=find(f[x]);
    	return f[x];
    }
    inline void merge(int x,int y)
    {
    	if(siz[x]>siz[y])swap(x,y);
    	a[y].reserve(siz[x]+siz[y]+1);
    	for(auto i:a[x])a[y].push_back(i),v[i]+=tag[x]-tag[y];
    	f[find(x)]=y;
    	siz[y]+=siz[x];
    }
    signed main()
    {
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)f[i]=i,siz[i]=1,a[i].push_back(i);
    	for(int i=1;i<=n;i++)cin>>v[i];
    	int op,x,y;
    	for(int i=1;i<=m;i++)
    	{
    		// if(clock()-st>0.45*CLOCKS_PER_SEC)cout<<i<<'\n';
    		cin>>op;
    		if(op==1)
    		{
    			cin>>x>>y;
    			if(find(x)!=find(y))merge(find(x),find(y));
    		}
    		else if(op==2)
    		{
    			cin>>x>>y;
    			tag[find(x)]+=y;
    		}
    		else
    		{
    			cin>>x;
    			cout<<v[x]+tag[find(x)]<<'\n';
    		}
    	}
    }

C. 梦幻布丁

  • 启发式合并
    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
    int color[1000005], ans;
    int fa[1000005];

    set<int> pos[1000005];

    void merge(int u, int v) {
    	for (int x : pos[u]) {
    		ans -= ((color[x - 1] == v) + (color[x + 1] == v));
    	}
    	for (int x : pos[u]) {
    		color[x] = v, pos[v].insert(x);
    	}
    	pos[u].clear();
    }

    int main() {
    	int n, m;
    	scanf("%d %d", &n, &m);
    	for (int i = 1; i <= n; i++) {
    		int x;
    		scanf("%d", &x);
    		fa[x] = x;
    		color[i] = x;
    		pos[x].insert(i);
    	}
    	ans = n;
    	for (int i = 1; i <= n; i++) {
    		if (color[i] == color[i - 1]) {
    			ans--;
    		}
    	}
    	while (m--) {
    		int op;
    		scanf("%d", &op);
    		if (op == 1) {
    			int x, y;
    			scanf("%d %d", &x, &y);
    			if (fa[x] == fa[y]) {
    				continue;
    			}
    			if (pos[fa[x]].size() > pos[fa[y]].size()) {
    				swap(fa[x], fa[y]);
    			}
    			merge(fa[x], fa[y]);
    		} else {
    			printf("%d\n", ans);
    		}
    	}
    }