CF1527D MEX Tree 题解

· · 题解

思路

如果一条路径的 \text {mex} = k，那么 0 \sim k-1 这些点一定在路径中出现过，并且一定在一条链上。如果不在一条链上，那么就不满足简单路径这一条件了。因此我们在从小到大加点的过程中如果发现一个点不在已求出的链上，那么比这个点编号大的 k 答案一定都是 0 了，因为不能同时把 0 \sim k-1 都一起走一遍，\text {mex} 也就一定 < k 了。

知道这个以后我们就得到了一个大致思路：从小到大枚举 \text {mex} 值 k，同时维护一条链的左、右端点，k 的答案就是包含已求出的链并且不包含 k 的所有路径数量。求完答案再判断当前点 k 是否能与 0 \sim k-1 继续构成一条链。如果能，那就更新链的左右端点，否则直接退出，其余输出 0 即可。

那么，如何判断 k 这个点在不在已求出的链上呢？我们可以暴力跳父亲，跳的时候同时打标记，这样就保证了每个点只会经过一次，时间为 \mathcal {O(n)}。如果 k 向上跳到的第一个被打了标记的点是 l 或者 r，那么从这两个端点延伸一定能到 k，k 也就一定能在链上。此时就可以继续更新了。

做完这步，还有一个问题就是：如何求满足条件的路径数量？可以先从 0 开始，\text {mex}=0 的路径数量就是不经过 0 的所有路径条数。可以树形 dp 解决，设 f_u 表示以 u 为根的子树中所有路径的数量，g_u 表示以 u 为根的子树中不经过 u 的所有路径条数。那么 g_u=\displaystyle\sum_{v \in son_u}f_v，f_u=g_u+size_u-1+\dfrac{\displaystyle\sum_{v \in son_u}size_v \displaystyle\sum_{p\in son_u,p \ne v}size_p}{2} 。f_u 的转移可以看成三部分：

  1. 所有的 f_v。
  2. 以 u 的子树中的任意一点为起点，u 为终点的路径。即 size_u-1。

这样我们就求出了 \text {mex}=0 的答案，为 g_0。因为链有两个端点，所以还要把 1 的答案求出来。对于 1，与一开始说的做法一样，跳父亲跳到 0，这时就已经有了链的雏形。那么，答案就是经过 0 且不经过 1 的路径条数，于是容斥一下，用所有经过 0 的路径减去既经过 1 又经过 0 的路径:f_0-g_0-size_1*(n-size_{now})。其中 now 是 1 在向上跳父亲时跳到的 0 的直连儿子。画下图就能理解了。

于是初始化左端点为 1，右端点为 0。每次枚举点 k，跳到链上后更新答案。怎么算答案？其实跟 1 的计算方式很像，包含以求出的链的路径且不包含 k 的路径条数。假如 k 跳到了 l，那么就是 (size_l-size_k) \times size_r（可能需要画图理解，有点抽象）。注意有 l,r 可能为 0，此时 size_r,size_l 就要减去多的一坨，此题就结束了。

其余细节见注释，赛时写的代码，可能有点丑，见谅。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,n,pp; 
int head[200005],cnt,k,vis[200005];
int ft[200005];
ll sz[200005];
ll f[200005],g[200005];
struct edge{
    int v,nxt;
}e[400005];
void add(int u,int v){
    e[++k].v=v;
    e[k].nxt=head[u];
    head[u]=k;
}
void dfs(int u,int fa){
    ll res=0,sum=0;
    sz[u]=1;
    ft[u]=fa;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa)continue;
        dfs(v,u);
        g[u]+=f[v];
        sz[u]+=sz[v];
        res+=sz[v];
        sum+=sz[v]*sz[v];
    }
    res*=res;
    f[u]+=g[u]+sz[u]-1+(res-sum)/2;//计算f[u]
}
void solve(){
    cin>>n;
    k=0;
    for(int i=0;i<=n;++i){
        sz[i]=0;
        head[i]=-1;
        f[i]=g[i]=vis[i]=0;
    }
    for(int i=1;i<n;++i){
        int a,b;
        cin>>a>>b;
        add(a,b);add(b,a);
    }
    dfs(0,-1);
    cout<<g[0]<<" ";
    int now=1;
    vis[0]=1;
    while(ft[now]!=0){//跳1的父亲
        vis[now]=1;
        now=ft[now];
    }
    vis[now]=1;
    pp=now;
    cout<<f[0]-g[0]-sz[1]*(n-sz[now])<<" ";
    int l=1,r=0;//维护链的端点
    bool flag=0;
    int epos=0;
    for(int i=2;i<=n;++i){
        now=i;
        int po=0;
        while((!vis[ft[now]])){//向上跳
            po++;
            vis[now]=1;
            now=ft[now];
        }
        int ffa=ft[now]; 
        if((ffa!=l)&&(ffa!=r)&&(po||(po==0&&(!vis[i])))){//不在链上
            flag=1;
            if(r!=0)cout<<sz[l]*sz[r]<<' ';
            else cout<<sz[l]*(sz[r]-sz[pp])<<" ";
            epos=i+1;
            break;
        }
        if(now==i&&po==0&&vis[i]){//已经在链上了，那就不可能把0~k-1走完，答案为0
            cout<<0<<" ";
            continue;
        }
        vis[now]=1;
        if(ffa==l){//更新左右端点
            if(r!=0)cout<<(sz[l]-sz[i])*sz[r]<<" ";
            else cout<<(sz[l]-sz[i])*(sz[r]-sz[pp])<<' ';
            l=i;
        }
        else{
            if(r!=0)cout<<(sz[r]-sz[i])*sz[l]<<' ';
            else cout<<(sz[r]-sz[pp]-sz[i])*sz[l]<<" ";
            r=i;
        }

    }
    if(flag){//不在链上全部输出0
        for(int i=epos;i<=n;++i)cout<<"0 ";
        cout<<endl;
        return;
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}