P15710 [JAG 2023 Summer Camp #2] Gemini Tree (Ver.Lapislazuli) 题解

· · 题解

首先容易发现树 T 上各个点的石头可以互相交换，也就是说可以随意排列。所以我们只关心绿色石头的数量 k。

易知 T 断开至多一条边能产生的连通块大小集合为 S=\{sz_i\mid i=1,2,\dots,n\}\cup\{n-sz_i\mid i=1,2,\dots,n\}。所以如果不管后面删叶子的事情，那么所有合法的 k 就是 S 的所有元素，答案即为 \sum_{k\in S}\binom nk。

但是还要删叶子，所以要减去删了之后不是双子树的方案。

令 D_k 为断开至多一条边能产生的、大小为 k 的连通块 的集合，断言：

若 |D_k|\geqslant2，则 D_k 中任取两相异元素 C_1,C_2，C_1\setminus C_2 与 C_2\setminus C_1 中均有叶子。 ::::info[证明] 显然 k\ne0,k\ne n，那么 D_k 中元素都是通过断边生成的。不妨给 T 随便定一个根，以边两端深度较大的点来指代边。记点 x 子树点集为 sub_x。 记生成 C_1,C_2 的这两条边对应点分别为 x_1,x_2。若 x_1=x_2，C_1,C_2 必定一个是 sub_{x_1}，一个是 T\setminus sub_{x_1} 子树，上述结论显然成立。对 x_1,x_2 的关系分讨：

  • 呈祖孙关系（\operatorname{lca}(x_1,x_2)\in\{x_1,x_2\}）

不妨设 x_1 为 LCA，则要么 C_1=sub_{x_1},C_2=T\setminus sub_{x_2}，要么 C_1=T\setminus sub_{x_1},C_2=sub_{x_2}。

前者 sub_{x_2} 中的叶子都 \in C_1\setminus C_2，T\setminus sub_{x_1} 中的叶子都 \in C_2\setminus C_1；后者显然成立。

所以如果 |D_k|\geqslant2，所有 k 个绿的方案都是合法的。构造则任取 D_k 两相异元素 C_1,C_2，删 C_1\setminus C_2 中的任意一个叶子。若为绿，则将剩余 k-1 个绿挪到新的 c_1；否则挪到 C_2。

现在只用管 |D_k|=1 了，设 D_k={C}。此时所有叶子的颜色都是固定的：C 中的叶子都必须是蓝色，其他叶子都必须是绿色。而且 C 中的叶子不能被任何 D_{k+1} 中的集合包含，T\setminus C 中的叶子必须被所有 D_{k-1} 中集合包含。

将叶子按 dfs 序排序，则每个连通块所包含的叶子形如 [l,r] 或 U\setminus[l,r]。这种东西就很容易判断包含 / 相交之类的了。时间复杂度 O(n\log n)，瓶颈在排序、lower_bound。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace IO {
    constexpr int bufsize = 230005;
    char buf[bufsize], *f1, *f2;
    char gtchar() {return f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++;}
    template<typename T> void read(T &ret)
    {
        int f = ret = 0;
        char ch = gtchar();
        while(!isdigit(ch)) f = ch == '-', ch = gtchar();
        while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
        if(f) ret = -ret;
    }
    template<typename T, typename ...t> void read(T &a, t &...b) {read(a), read(b...);}
}using IO::read;
template<typename t, typename T = t> void chmax(t &a, const T &b) {if(a < b) a = b;}
template<typename t, typename T = t> void chmin(t &a, const T &b) {if(a > b) a = b;}
constexpr int maxn = 1e5 + 5, mod = 998244353;
int Add(int a, const int &b) {return (a += b) >= mod? a - mod: a;}
int n, cnt, dfn[maxn], sz[maxn];
ll fac[maxn], inv[maxn];
vector<int> g[maxn], leaf;
struct range {
    int l, r, mode;//0:[l,r] 1:[0,l),(r,leaf.size()-1]
    int size() {return mode? leaf.size() - (r - l + 1): r - l + 1;}
};
vector<range> D[maxn];
void dfs(int k, int pre)
{
    sz[k] = 1, dfn[k] = ++cnt;
    if(g[k].size() == 1) leaf.push_back(dfn[k]);
    for(int i : g[k]) if(i != pre) dfs(i, k), sz[k] += sz[i];
}
void dfs2(int k, int pre)
{
    int l = lower_bound(leaf.begin(), leaf.end(), dfn[k]) - leaf.begin();
    int r = lower_bound(leaf.begin(), leaf.end(), dfn[k] + sz[k]) - leaf.begin() - 1;
    // printf("%d:%d,%d\n", k, l, r);
    D[n - sz[k]].push_back({l, r, 1});
    D[sz[k]].push_back({l, r});
    for(int i : g[k]) if(i != pre) dfs2(i, k);
}
int binom(int a, int b) {return a >= b && b >= 0? fac[a] * inv[b] % mod * inv[a - b] % mod: 0;}
bool inter(range a, range b)
{
    if(a.mode && b.mode) return !(min(a.l, b.l) == 0 && max(a.r, b.r) == leaf.size() - 1 && max(a.l, b.l) - 1 <= min(a.r, b.r));
    if(b.mode) swap(a, b);
    if(a.mode) return !(a.l <= b.l && b.r <= a.r);
    return max(a.l, b.l) <= min(a.r, b.r);
}
bool contain(range a, range b)
{
    if(a.mode && b.mode) return b.l <= a.l && a.r <= b.r;
    if(a.mode) return b.r < a.l || b.l > a.r;
    if(b.mode) return a.l == 0 && a.r == leaf.size() - 1;
    return a.l <= b.l && b.r <= a.r;
}
int main()
{
    read(n);
    inv[0] = inv[1] = fac[0] = fac[1] = 1;
    for(int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    for(int i = 2; i <= n; i++) inv[i] = mod - mod / i * inv[mod % i] % mod;
    for(int i = 2; i <= n; i++) inv[i] = inv[i - 1] * inv[i] % mod;
    for(int i = 1, x, y; i < n; i++)
    {
        read(x, y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0);
    dfs2(1, 0);
    int ans = 0;
    for(int i = 0; i <= n; i++) if(D[i].size()) ans = Add(ans, binom(n, i));//, printf("i(%d)\n", i);
    // printf("%d\n", ans);
    for(int i = 1; i < n; i++) if(D[i].size() == 1)
    {
        auto now = D[i][0];
        // printf("now:%d %d %d\n", now.l, now.r, now.mode);
        int tmp = binom(n - leaf.size(), i - int(leaf.size() - now.size()));
        int f = 1;
        for(auto ele : D[i + 1]) if(inter(ele, now)) {f = 0; break;}
        now.mode ^= 1;
        if(f) for(auto ele : D[i - 1]) if(!contain(ele, now)) {f = 0; break;}
        if(f) ans = Add(ans, mod - tmp);//, printf("ban %d(%d)\n", tmp, i);
    }
    printf("%d\n", ans);
    return 0;
}

::::