CF1527D

AsunderSquall · 2021-07-06 19:53:04 · 题解

题意

给一棵 n 个节点的树，标号从 0 到 n-1，对于任意 k，求点对 u,v 的数量，使得 \text{Mex}_{ w \in path(u,v)}=k。

题解

whk 了两个月之后感觉自己已经没有脑子了（奇怪，说得好像我曾经有过一样）。

首先考虑在链上怎么做。我们从 0 开始往上推，比如我们现在枚举到了 x。
那么我们发现 0 到 x 的数一定在一个区间 [l,r] 内，于是我们知道 \text{Mex}> x 的路径数有 l\times(n-r+1) 条。然后以此类推，最后输出的时候减一下即可。

然后我们考虑怎么上树。首先，如果 0 到 x 的数不在同一条链上，那么能够同时经过这些数的路径一定不存在。否则显然 0 到 x-1 也一定是一条链，那么我们维护这条链和链两端的节点数即可。

我维护链的方法是，如果当前点不在链上，就不停地跳父亲直到找到已经在链上的点。如果是端点，那么就产生了新的端点，否则一定不是一条链。链两端的节点数可以直接用子树大小。

代码：

实现非常丑陋（最开始的时候甚至把一个 bool 数组能干的事用 set 来做，我果然没脑子）

int n,ans,m,l,r,L,R;
int a[N],b[N],sz1[N],sz2[N],FA[N],S[N];
vector<int> T[N];
void dfs(int u,int fa,int sz[])
{
    FA[u]=fa;
    sz[u]=1;for (int v:T[u]) if (v!=fa) dfs(v,u,sz),sz[u]+=sz[v];
}
signed main()
{
    int qwq;rd(qwq);while (qwq--)
    {
        rd(n);
        for (int i=0;i<=n;i++) T[i].clear();
        for (int i=1,x,y;i<n;i++) rd(x),rd(y),T[x].push_back(y),T[y].push_back(x);
        for (int i=0;i<=n+1;i++) a[i]=0,sz1[i]=sz2[i]=0,S[i]=0;
        l=r=0;dfs(0,-1,sz1);a[0]=n*(n-1)/2;
        a[1]=2*n-2;for (int v:T[0]) a[1]+=(n-1-sz1[v])*sz1[v];a[1]/=2;
        dfs(1,-1,sz2);l=1;r=0;L=sz1[l];R=sz2[r];a[2]=L*R;
        int x=0;while (x!=1) S[x]=1,x=FA[x];S[1]=1;
        for (int k=2;k<n;k++)
        {
            if (S[k]) {a[k+1]=L*R;continue;}
            int x=k;
            while (!S[x]) x=FA[x];
            if (x==l) 
            {
                int x=k;while (x!=l) S[x]=1,x=FA[x];
                l=k,L=sz1[l],a[k+1]=L*R;
            } else if (x==r) 
            {
                int x=k;while (x!=r) S[x]=1,x=FA[x];
                r=k;R=sz2[r],a[k+1]=L*R;
            } else break;
        }
        for (int i=0;i<=n;i++) a[i]-=a[i+1],cout<<a[i]<<" ";
        puts("");
    }
}