2020 wannafly camp day5 B Bitset Master —— 思维_综合

题目链接：点我啊╭(╯^╰)╮

题目大意：

     $n$ 个点， $n ? 1$ 条边， $m$ 次操作
    每个点有一个集合， $s e t$ 里最初只有自己
    每次操作将第 $p_i$ 条边的两个点的 $s e t$ 合并
    合并后两个点的 $s e t$ 为合并后的 $s e t$
    最后问每个点被几个 $s e t$ 包含

解题思路：

     $f [u] 、 f [v]$ 表示 $u$ 与 $v$ 的 $s e t$ 大小，合并后：
     $\bigcap f[v]$
     $\bigcap f[v]$ 表示两个集合交，也就是上次合并的大小

问题来了，怎么求每个点去过几个 $s e t$ 呢？？？
题解说倒过来求就是了

    我的理解是倒过来的意义在于每次操作都是对后缀处理
     $f [u] 、 f [v]$ 表示 $u$ 与 $v$ 的能去多少个 $s e t$ ，合并后：
     $\bigcap f[v]$
     $\bigcap f[v]$ 表示两个点都能去的 $s e t$ 个数

    因为是倒过来求
     $\bigcap f[v]$ 表示的就是完成后缀操作后
    两者能去的 $s e t$ 个数

我还能说什么

核心：正难则反

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <int,int>;
const int maxn = 5e5 + 5;
int n, m, p[maxn], f[maxn];
int gu[maxn], gv[maxn], g[maxn];int main() {scanf("%d%d", &n, &m);for(int i=1; i<n; i++) scanf("%d%d", gu+i, gv+i);for(int i=1; i<=m; i++) scanf("%d", p+i);for(int i=1; i<=n; i++) f[i] = 1;for(int i=m, u, v; i; i--){u = gu[p[i]], v = gv[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++) printf("%d%c", f[i], "\n "[i<n]);
}