Wannafly Winter Camp 2020 Day 5B Bitset Master – 时间倒流

有 \(n\) 个点的树，给定 \(m\) 次操作，每个点对应一个集合，初态下只有自己。

第 \(i\) 次操作给定参数 \(p_i\)，意为把 \(p_i\) 这条边的两个点的集合合并，并分别发配回这两个点

最后求每个点出现在多少个集合中

Solution

换个问题，求每个集合最后的大小。我们发现，如果将 \(u,v\) 合并，那么 \(f[u]=f[v]=f[u]+f[v]-f[u] \bigcap f[v]\)

而 \(f[u] \bigcap f[v]\) 之和上一次 \(u,v\) 合并的结果有关，于是我们可以对每条边单独记录一个数，表示上一次合并这条边的结果

回到原问题，我们发现，每个点被哪些集合包含，只需要倒叙处理新问题就可以得到原问题的答案

#include <bits/stdc++.h>
using namespace std;const int N = 1000005;int n,m,p[N],x[N],y[N],f[N],g[N];void read(int &x) {
    scanf("%d",&x);
}void write(int x,int flag) {
    printf("%d",x);
    if(flag==0) putchar(' ');
    else puts("");
}signed main() {
    read(n);read(m);
    for(int i=1;i<n;i++) read(x[i]), read(y[i]);
    for(int i=1;i<=m;i++) read(p[i]);
    for(int i=1;i<=n;i++) f[i]=1;
    for(int i=m;i>=1;--i) {
        int u=x[p[i]], v=y[p[i]];
        f[u]=f[v]=f[u]+f[v]-g[p[i]];
        g[p[i]]=f[u];
    }
    for(int i=1;i<=n;i++) write(f[i],i==n);
}