啊～啊～啊咦～啊咦～哦→啊↑啊↓啊～嗯～哎哎↑哎哦哎嗯～哦啊~爱↖爱↑爱↗爱↑爱↑

11400F · 2024-12-25 23:46:54 · 题解

TECHNOPOLIS 2085 题解

我是中二吃，看到题目和背景那啪的一下就点进来了。

要使在新的树 T^{\prime} 上一些关键点的 LCA 和原树相同，很容易就会想到虚树，也就是说，对于关键点集 S，T 和 T^{\prime} 的虚树是相同的。

那么我们首先就可以把这棵虚树给建好（设这棵虚树有 k 个点）。然后将剩下的点插到虚树里，造出来一棵新树。

我们这里假设新树树根为虚树的根。

具体地说，把剩下的点插到原来的虚树中，就只有两种情况：要么把点加到虚树边上；要么不在虚树边上加点，等把加在虚树边上的点加完了之后再把这棵虚树上的点和这些散点连边使它们连通。

• 首先讨论把点加到虚树边上的情况：

  假设我们把 i 个点插入到虚树树边上。因为我们要选 i 个点，所以选点的方案数就是 C_{n-k}^{i}。然后插到虚树边上。注意到，我们每把一个点插入到某条虚树边上，这条边就会因为中间加了一个点而被被断为 2 条。并且因为最开始这棵虚树是只有 k-1 条边的，所以，插入边的方案数就为 (k-1)\cdot k\cdot(k+1)\cdots(k+i-2) = \displaystyle\prod_{p=1}^{i}(k-2+p) = \frac{(k+i-2)!}{(k-2)!}。而因为 m \ge 2，所以 k 也一定 \ge 2，不用担心越界。

  所以把点加到虚树边上的情况就有 \displaystyle C_{n-k}^{i} \cdot \frac{(k+i-2)!}{(k-2)!} 种。

• 然后讨论把剩下的散点和这棵已经加完了 i 个点的新树连边的情况：

  问题就转化成了：有一棵点数为 k+i 的树，和一堆总数为 n-k-i 的散点。现在需要连接 n-k-i 条边使这些散点和树连通。求连边的方案数。

  在这之前，我们引入由 Prüfer 序列引出的一个公式：

  现在有一个 n 个点和 m 条边的有标号无向图，其中有 k 个连通块。第 i 个连通块的大小为 s_i。我们要连接 k-1 条边使这个图连通。求连边的方案数。

  方案数即为：

  n^{k-2} \cdot \displaystyle \prod_{i=1}^{k} s_i

  （具体证明详见 OI-Wiki，这里不作过多说明。）

  将其带入可得：答案即为 n^{n-k-i-1}\cdot\displaystyle\prod_{i=1}^{n-k-i+1} s_i = n^{n-k-i-1}(k+i)。

  这里有一种特殊情况：当 i=n-k 时，那么显然，就是没有点为散点的情况，方案数为 1。

  因为情况复杂，我们假设这种情况的答案为 out_{n, k, i}（此时新树树根为虚树根，并且原树点 n 个、虚树点 i 个、把 i 个点放到了虚树树边上）。

所以新树树根为虚树根，原树点 n 个、虚树点 k 个的散点答案 out_{n, k, i} 和总答案 res_{n, k} 就为：

而如果 k < n，就说明有可能有新树树根不为虚树树根的情况，那么我们就可以钦定一个新树根，它的儿子唯一，为原来的虚树树根。一共有 n-k 种钦定方式。每一种钦定方式的答案为 res_{n, k+1}，因为新加了一个点到虚树中。所以新树树根不为虚树树根的总方案数为 (n-k)\cdot res_{n, k+1}。

所以最终的总答案就为：

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+6;
const int M = 2e6+6;

struct Edge{
    int to, nxt;
}edge[M];
int h[N], cnt;
void _add(int u, int v) {edge[++cnt] = {v, h[u]}; h[u] = cnt; }
void add(int u, int v) {_add(u, v), _add(v, u);}
int dep[N], dfn[N], dfnidx, anc[N][21], keyp[M];
int lim, m, len;
void dfs(int x, int fa){
    dfn[x] = ++dfnidx;
    dep[x] = dep[fa] + 1;
    anc[x][0] = fa;
    for(int i=1;i<=lim;i++) anc[x][i] = anc[anc[x][i-1]][i-1];
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to; if(v == fa) continue;
        dfs(v, x);
    }
}
int getlca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    int sa = dep[x] - dep[y];
    for(int i=lim;i>=0&&sa;i--){
        if(sa&(1<<i)) sa -= (1<<i), x = anc[x][i];
    }
    if(x==y) return x;
    for(int i=lim;i>=0;i--){
        if(anc[x][i]^anc[y][i]) x = anc[x][i], y = anc[y][i];
    }
    return anc[x][0];
}
bool cmp(int x, int y){
    return dfn[x] < dfn[y];
}
void init_imagtree(){
    for(int i=1;i<=m;i++) cin>>keyp[i];
    sort(keyp+1, keyp+1+m, cmp);
    len = m;
    for(int i=1;i<m;i++)
        keyp[++len] = getlca(keyp[i], keyp[i+1]);
    sort(keyp+1, keyp+1+len);
    len = unique(keyp+1, keyp+1+len) - keyp - 1;
}
// 其实上面那一堆都只是用来求最开始的虚树有多少个点。应该有更好的方法。

typedef long long ll;
const ll mod = 998244353;
ll fact[M], invfact[M];

ll ksm(ll bas, ll x){
    ll ans = 1;
    while(x){
        if(x&1) ans = ans * bas % mod;
        bas = bas * bas % mod; x >>= 1;
    }
    return ans;
}

ll C(ll nn, ll mm){
    return fact[nn]*invfact[mm]%mod*invfact[nn-mm]%mod;
}
ll calc(int n, int k){
    ll ans = 0;
    for(int i=0;i<=n-k;i++){
        ans = (ans + 
              C(n-k, i) * fact[k+i-2] % mod * invfact[k-2] % mod * 
              ((i == n-k)? 1: ksm(n, n-k-i-1) * (k+i) % mod) % mod)
              % mod;
    }
    return ans;
}

int n;
void init_fact(){
    fact[0] = invfact[0] = 1;
    for(int i=1;i<=n;i++)
        fact[i] = fact[i-1] * i % mod;
    invfact[n] = ksm(fact[n], mod-2);
    for(int i=n-1;i>=1;i--)
        invfact[i] = invfact[i+1] * (i+1) % mod;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    lim = __lg(n) + (__builtin_popcount(n) != 1);
    // cout<<lim<<'\n';
    int u;
    for(int i=2;i<=n;i++){
        cin>>u; add(u, i);
    }
    dfs(1, 0);
    init_imagtree();

    init_fact();
    ll ans = 0;
    ans += calc(n, len);
    if(len < n) ans = (ans + (n-len) * calc(n, len+1) % mod) % mod;
    cout<<ans;
    return 0;
}

为了一道 2085 学了好多啊 qwq，我还要打 2085。