CF1796E Colored Subgraphs 题解

OMG_wc · 2023-03-06 17:19:17 · 题解

题意是对一棵无根树，进行某种树链剖分后，使得链长的最小值最大，求出这个最大值。

先想想以 1 为根怎么做？当然是从叶子开始，每条链往上生长，一个点如果有多个儿子，会贪心地选择最短链往上生长。

记 f_u 表示 u 的每个儿子的所在的链长集合，其中链长指的是链中点的个数，叶节点的 f_u=\varnothing。

那么 u 会归属于其中的最短链，而次短链开始的其他链长度就永远停留在了原地，所以最终答案不会超过所有 f_u 里的次小值。

最终答案也不会超过 f_1 的最小值加 1，那么以 1 为根的答案就算出来了。

然后用换根法来算其他结点为根时的答案，需要一个全局multiset维护所有点的次小值集合。具体而言，把根从 u 切换到儿子 v 时，先在 f_u 里删除 v 对 u 的贡献，然后在 f_v 里加上 u 对 v 的贡献，处理完 v 子树后再还原。

时间复杂度 O(n\log n)，代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 200005;

vector<int> G[N];
multiset<int> f[N]; 
multiset<int> se;   
int ans;

int getlen(int u) {
    return f[u].size() == 0 ? 1 : *f[u].begin() + 1;
}
void add(int u, int val) {
    if (f[u].size() >= 2) se.erase(se.find(*next(f[u].begin())));
    f[u].insert(val);
    if (f[u].size() >= 2) se.insert(*next(f[u].begin()));
}
void del(int u, int val) {
    if (f[u].size() >= 2) se.erase(se.find(*next(f[u].begin())));
    f[u].erase(f[u].find(val));
    if (f[u].size() >= 2) se.insert(*next(f[u].begin()));
}

void dfs1(int u, int fa) {
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        f[u].insert(getlen(v));
    }
    if (f[u].size() >= 2) se.insert(*next(f[u].begin()));
}
void dfs2(int u, int fa) {
    ans = max(ans, min(getlen(u), se.empty() ? INF : *se.begin()));
    for (auto v : G[u]) {
        if (v == fa) continue;
        del(u, getlen(v));
        add(v, getlen(u));
        dfs2(v, u);
        del(v, getlen(u));
        add(u, getlen(v));
    }
}

int main() {
    int _;
    scanf("%d", &_);
    while (_--) {
        int n;
        scanf("%d", &n);
        se.clear();
        for (int i = 1; i <= n; i++) G[i].clear(), f[i].clear();
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        ans = 0;
        dfs1(1, 0);
        dfs2(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}