[计数] [容斥] P6277 [USACO20OPEN] Circus P

· · 题解

题意：n 个点的树，有 k 头不同的牛分布在不同的点上，可以操作一头牛向相邻点移动，要求不能有牛在相同节点。状态 A 若可以经过若干次操作到达状态 B 则它们在同一等价类，对每个 k\in[1,n] 求有多少种不同等价类。n\le 10^5。

感性理解万岁！其实是太菜了 qwq。

首先有如下想法：

  1. 忽略标号，则所有状态互相可达。很显然。所以不妨让牛移动到 1\dots k 上。
  2. 对于两个位置 x,y，若可以在不影响其他牛的情况下交换上面的牛，就连边 x,y。那么存在传递性，因为可以依次 (x,y),(y,z),(x,y) 以做到 (x,z)。于是关系图是若干团，答案即为 \frac {k!}{\prod s_i!}，s_i 为团大小。
  3. “不影响其他牛”其实毫无意义，因为只需交换后倒置整个过程，即可消除影响。

现在考察两头牛 a,b 可以交换的条件，发现形如将 a 移到空位 c、将 b 移到 a 原位、将 a 移到 b 原位。

拓展一下，对于一条链 s\to t，令其满足 s,t 是非 2 度点，链上其它点均是二度点。很自然地先将牛分别移动到 s,t 子树，那么假如此时 s,t 子树均填满了的话（此处子树不包括 s,t），两边子树的牛不可能交换成功。否则存在一个空隙，能凭借它交换两端可以到达链上的点。未填满的条件即为 k<n-len，len 是链长。

考察链在树上形态：在树上划出这些链，它们首尾相接，并且每条边恰被覆盖一次。

考察链在关系图上形态：称不满足条件的链为非法链，反之为合法链，合法链构成若干连通块，则每个连通块都在同一个团，又因为非法链的存在所以不同连通块在不同的团。

可能有一些团大小为 1 没被考虑到，但是问题不大，因为不影响答案。只考虑 \ge 2 的团，它们一定是存在交换关系的，也就是对应着连通块。

唯一的问题是怎么求出连通块对应的团的大小，直接统计貌似很困难。正难则反，转而用相接的非法链去刻画这个团，对于一条相接的非法链 a_i\to b_i，令 a_i 在连通块内而 b_i 在连通块外。那么向 a_i 子树填牛，至多填 A_i-1 个，也就是说 k-(A_i-1) 头牛必然在团外。注意并非 a_i，因为恰在 a_i 上的这头牛显然也是无法参与团内交换的。

这样算不重不漏，因为每一次相当于排除 b_i 方向的一些团，每次排除的团的不会重复，且总和恰好是其它团。

于是团大小即为：

k-\sum k-(A_i-1)=k-\sum k-(n-B_i-len_i+1)=k-((k-n+1)cnt+\sum B_i+len_i-2)

其中 cnt 是相邻非法链数量，注意到 \sum B_i+len_i-2 即为连通块外点数即 n-siz，所以只需维护一下 cnt,siz 即可。

时光倒流 k 使得删边变加边，所以 cnt,siz 是容易用并查集维护的。同时，连通块个数是非法链条数加一，一条非法链存活时间为其长度，所以所有时刻连通块总数是非法链长度级别的，也就是 O(n)，直接拿个 set 维护即可。复杂度 O(n\log n)。

当然可以精细实现 O(n)，在连通块合并时直接维护答案应该就行了？

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 5, mod = 1e9 + 7;
int n, u, v, du[N], rot, m, ans[N], jc[N], jcinv[N];
int fa[N], siz[N], cnt[N]; 
vector<int> to[N];
set<int> s;
struct dist{int x, y, w;};
vector<dist> jjdw[N];

inline int qstp(int a, int k) {int res = 1; for(; k; a = a * a % mod, k >>= 1) if(k & 1) res = res * a % mod; return res;}
inline void dfs(int u, int from, int lst, int len){
    if(du[u] == 2){
        for(auto v : to[u]) if(v ^ from) dfs(v, u, lst, len + 1); 
    }
    else{
        fa[u] = u, siz[u] = 1, s.insert(u);
        if(lst) jjdw[len].push_back({u, lst, len}), ++cnt[u], ++cnt[lst];
        for(auto v : to[u]) if(v ^ from) dfs(v, u, u, 2);
    }
}
inline int find(int u) {return fa[u] == u ? u : fa[u] = find(fa[u]);}
inline void mer(int x, int y, int w){
    int fx = find(x), fy = find(y);
    fa[fx] = fy;
    siz[fy] += siz[fx] + w - 2;
    cnt[fy] += cnt[fx] - 2;
    s.erase(fx);
}
signed main(){
    jc[0] = jcinv[0] = 1;
    for(int i = 1; i < N; ++i) jcinv[i] = qstp(jc[i] = jc[i - 1] * i % mod, mod - 2);

    cin >> n;
    for(int i = 1; i < n; ++i){
        scanf("%lld%lld", &u, &v);
        to[u].push_back(v), to[v].push_back(u);
        ++du[u], ++du[v];
    }
    for(int i = 1; i <= n; ++i) if(du[i] == 1) rot = i;
    dfs(rot, 0, 0, 0);
    ans[n] = jc[n];
    for(int k = n - 1; k; --k){
        for(auto _ : jjdw[n - k - 1]) mer(_.x, _.y, _.w);
        ans[k] = jc[k];
        for(auto i : s){
            int mb = k - ((k - n + 1) * cnt[i] + n - siz[i]);
            ans[k] = ans[k] * jcinv[mb] % mod;
        }
    }
    for(int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
    return 0;
}