P11039 TECHNOPOLIS 2085 题解

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

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

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

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

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

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

假设我们把个点插入到虚树树边上。因为我们要选个点，所以选点的方案数就是。然后插到虚树边上。注意到，我们每把一个点插入到某条虚树边上，这条边就会因为中间加了一个点而被被断为条。并且因为最开始这棵虚树是只有条边的，所以，插入边的方案数就为。而因为，所以也一定，不用担心越界。

所以把点加到虚树边上的情况就有种。
然后讨论把剩下的散点和这棵已经加完了个点的新树连边的情况：

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

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

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

方案数即为：
$n^{k-2} \cdot \displaystyle \prod_{i=1}^{k} s_i$
（具体证明详见OI-Wiki，这里不作过多说明。）

将其带入可得：答案即为。

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

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

所以新树树根为虚树根，原树点个、虚树点个的散点答案和总答案就为：

$out_{n, k, i} = \left\{ \begin{aligned} &n^{n-k-i+1}(k+i) &(i < n-k)\\ &1 &(i=n-k) \end{aligned} \right.\\ res_{n, k} = \displaystyle \sum_{i=0}^{n-k} C_{n-k}^{i} \cdot \frac{(k+i-2)!}{(k-2)!}\cdot out_{n, k, i}$

所以最终的总答案就为：

$res_{n, k} + [n<k] \cdot (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 学了好多啊，~~我还要打 2085。~~