题解：CF2107D Apple Tree Traversing

sunkuangzheng · 2025-05-06 10:08:20 · 题解

\mathcal O(n \sqrt n) 做法

为了让字典序最大，我们每次操作会贪心的选择一条端点最大的直径。找端点最大的直径可以直接在两遍 dfs 时对 pair (dep_u,u) 取 \max。

考虑每次暴力 dfs 找出直径删除后递归剩余部分，我们将证明这样暴力递归的复杂度是 \mathcal O(n \sqrt n) 的。

树的所有直径交于一点或一条边，因此删除直径后剩余部分的直径长度至少减少 1。注意这个点不一定是点分治里树的重心。
令 l_i 表示第 i 层递归的最大直径长度。显然 \sum l_i \le n 且序列 l 单调递减，因此 l 中的元素个数是 \mathcal O(\sqrt n) 级别的。
每一层递归的枚举总量是 \mathcal O(n)，因此总复杂度为 \mathcal O(n \sqrt n)。

容易根据上述证明构造一组卡满复杂度的数据：将长度为 1,3,5,7,\ldots,\sqrt n 的链的中点相连即可。

\mathcal O(n \log n) 做法

该做法最早在验题时由 @沉石鱼惊旋发现，orz /bx。

考虑 dp 求解树的直径的过程，设 f_u 表示从 u 往下的子树最长链，g_u 表示和 f_u 不在一个子树的最长链，则树的直径是 \max \limits_{u=1}^n \{f_u + g_u\}。

关键观察是，如果某次树的直径是 (u,v)，那么路径 (\operatorname{lca}(u,v),\text{root}) 的有效长度一定不超过 (u,v)（有效指的是从 lca 向上遇到第一个已经删掉的点就退出）。这就意味着暴力更改路径 (\operatorname{lca}(u,v),\text{root}) 的有效部分的复杂度仍然是均摊线性的。

于是做法就很简单了：对于每个节点 u 用 std::set 存储其每个儿子子树的最长链即可维护 f_u,g_u，全局维护一个堆存储所有点的 f_u,g_u 信息。每次找到一条直径 (u,v) 时，暴力修改路径 (u,v) 和 (\operatorname{lca}(u,v),\text{root}) 的有效部分。修改总次数为 \mathcal O(n)，因此总复杂度为 \mathcal O(n \log n)。

#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
using pi = pair<int,int>;
using ti = tuple<int,int,int,int>;
int T,n,u,v,del[N],fa[N],ct;  vector<int> g[N]; set<pi> t[N];
void dfs(int u,int f){
    t[u].emplace(0,u),fa[u] = f;
    for(int v : g[u]) if(v != f){
        dfs(v,u); auto [x,y] = *--t[v].end();
        t[u].emplace(x+1,y);
    }
}ti gt(int u){
    assert(t[u].size() >= 1);
    if(t[u].size() == 1) return {0,u,u,u};
    auto [x,y] = *--t[u].end();
    auto [p,q] = *--(--t[u].end());
    return {x + p,max(y,q),min(y,q),u};
}void los(){
    cin >> n;
    for(int i = 1;i <= n;i ++) g[i].clear(),del[i] = 0,t[i].clear();
    for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
    ct = 0,dfs(1,0); priority_queue<ti> q;
    for(int i = 1;i <= n;i ++) q.emplace(gt(i));
    while(q.size()){
        auto [di,u,v,d] = q.top(); q.pop();
        if(del[d] || ti{di,u,v,d} != gt(d)) continue;
        cout << di + 1 << " " << u << " " << v << " ";
        while(u != d) del[u] = 1,u = fa[u];
        while(v != d) del[v] = 1,v = fa[v];
        del[d] = 1; 
        auto [x,y] = *--t[d].end();
        while(fa[d] && !del[fa[d]]){
            d = fa[d];
            if(t[d].count({++x,y})) t[d].erase({x,y});
            q.emplace(gt(d));
            if(fa[d]){
                auto [a,b] = *--t[d].end();
                t[fa[d]].emplace(a+1,b);
            }
        }
    }cout << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}