CF1527D MEX Tree 题解

题目链接：CF1527D MEX Tree

题意：

本题有多组测试数据。

给出一棵 $n$ 个点的树，点从 $0$ 到 $n - 1$ 编号。定义一条路径的权值是路径上所有点编号的 $\operatorname{mex}$。对于每个 $0\le i\le n$ 求出 $\operatorname{mex}$ 为 $i$ 的路径有几条。注意，这里统计的路径需要包括至少一条边。

一个集合的 $\operatorname{mex}$ 定义为最小的不在集合中的非负整数。

数据范围：

$2 \le n \le 2\times 10^5, \sum n_i \le 2\times 10^5$ 。

先考虑在链上怎么做。我们从 $0$ 开始往上推，设当前枚举到了 $x$ 。

可以发现 $0$ 到 $x$ 的数一定会在一个区间 $[l,r]$ 内，根据乘法原理可知 $\mathrm{mex} > x$ 的路径数有 $l\times (n - r + 1)$ 条。

接着考虑在树上怎么做。显然，到了树上，$0$ 到 $x$ 就很难在同一条链上了。

不过我们注意到，如果 $0$ 到 $x$ 不在一条链上，那么能通过这些数的路径也不存在。

否则一定可以用一条链连接 $0$ 到 $x$ ，于是我们可以维护这条链和链两端的节点数。

具体地，如果当前点不在链上，就不停跳 fa 直到找到已经在链上的点。

如果这个点是端点，那么更新端点，否则一定不是一条链。

时间复杂度 $\mathcal{O}(n\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

vector<int> T[N];
int n,ans,m,l,r,L,R,a[N],b[N],sz1[N],sz2[N],fa[N],S[N];
void dfs(int u, int f, int sz[])
{
    fa[u] = f; sz[u] = 1;
    for(int v : T[u]) if(v != f) { dfs(v, u, sz); sz[u] += sz[v]; }
}
void solve()
{
    cin >> n;
    for(int i = 0; i <= n; i++) T[i].clear();
    for(int i = 1, x,y; i < n; i++)
    {
        cin >> x >> y;
        T[x].push_back(y); T[y].push_back(x);
    }
    for(int i = 0; i <= n + 1; i++) { a[i] = sz1[i] = sz2[i] = 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 t = k; while(!S[t]) t = fa[t];
        if(t == 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(t == 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] << " \n"[i == n]; }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve(); // Great!
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/LilliaAsupurei/solution-cf1527d