题解：CF1527D MEX Tree

chrisgr · 2025-10-01 21:05:38 · 题解

某模拟赛 T1，赛后发现爆标（题解是 \operatorname{LCA} 做法），遂来写题解。

我们发现不含 0 的路径 \operatorname{mex} = 0。含 0 的路径 \operatorname{mex} > 0，所以可以先单独计算不含 0 的路径数，求出 ans_0。
对于含 0 的路径，我们可以从 1 开始枚举新添的数，并把它尝试添进答案路径中，维护答案。我们发现，添加进入答案序列并不需要 \operatorname{LCA}，只需要暴力跳父亲，因为每个点最多访问一次，所以复杂度为均摊 \operatorname{O}(n)。爆标了！！

code

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n, f[N], siz[N];
long long ans[N];
bool book[N];
vector<int> mp[N];
inline dfs(int x, int y) {
    f[x] = y, siz[x] = 1;
    for(int i = mp[x].size() - 1; ~i; --i) {
        int to = mp[x][i];
        if(to ^ y) {
            dfs(to, x);
            if(!x) ans[0] += 1ll * (siz[to] - 1) * siz[to] >> 1;
            siz[x] += siz[to];
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        if(n == 1) {
            puts("0 0");
            continue;
        }
        for(int i = n - 1; i; --i) {
            int u, v;
            cin >> u >> v;
            mp[u].push_back(v), mp[v].push_back(u);
        }
        dfs(0, 0);
        int l = 1, r = 0, now = 1, as = 1;
        while(f[now]) book[now] = 1, now = f[now];
        book[now] = 1, book[0] = 1;
        while(book[as]) ++as;
        siz[0] -= siz[now];
        ans[1] = 1ll * siz[0] * (siz[now] - siz[1]);
        int sz = siz[0];
        for(int i = mp[0].size() - 1; ~i; --i) {
            int to = mp[0][i];
            if(to ^ now) sz -= siz[to], ans[1] += 1ll * sz * siz[to];
        }
        for(int i = as; i < n; i = as) {
            int ii = i;
            while(!book[f[ii]]) book[ii] = 1, ii = f[ii];
            book[ii] = 1;
            if(f[ii] == l) {
                while(book[as]) ++as;
                ans[i] = 1ll * siz[r] * (siz[l] - siz[i]);
                l = i;
            } else if(f[ii] == r) {
                while(book[as]) ++as;
                ans[i] = 1ll * siz[l] * (siz[r] - siz[i]);
                r = i;
            } else break;
        }
        ans[as] = 1ll * siz[l] * siz[r];
        for(int i = 0; i <= n; ++i) {
            printf("%lld ", ans[i]);
            ans[i] = book[i] = siz[i] = f[i] = 0;
            mp[i].clear();
        }
        putchar('\n');
    }
    return 0;
}