专栏文章

题解：CF2107D Apple Tree Traversing

ssunkuangzheng
CF2107D题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mipedrho
此快照首次捕获于
2025/12/03 10:38
3 个月前
此快照最后确认于
2025/12/03 10:38
3 个月前
查看原文

O(nn)\mathcal O(n \sqrt n) 做法

为了让字典序最大，我们每次操作会贪心的选择一条端点最大的直径。找端点最大的直径可以直接在两遍 dfs 时对 pair (depu,u)(dep_u,u) 取 max⁡\max。
考虑每次暴力 dfs 找出直径删除后递归剩余部分，我们将证明这样暴力递归的复杂度是 O(nn)\mathcal O(n \sqrt n) 的。
  • 树的所有直径交于一点或一条边，因此删除直径后剩余部分的直径长度至少减少 11。注意这个点不一定是点分治里树的重心。
  • 令 lil_i 表示第 ii 层递归的最大直径长度。显然 ∑li≤n\sum l_i \le n 且序列 ll 单调递减，因此 ll 中的元素个数是 O(n)\mathcal O(\sqrt n) 级别的。
  • 每一层递归的枚举总量是 O(n)\mathcal O(n)，因此总复杂度为 O(nn)\mathcal O(n \sqrt n)。
容易根据上述证明构造一组卡满复杂度的数据：将长度为 1,3,5,7,…,n1,3,5,7,\ldots,\sqrt n 的链的中点相连即可。

O(nlog⁡n)\mathcal O(n \log n) 做法

该做法最早在验题时由 沉石鱼惊旋发现，orz /bx。
考虑 dp 求解树的直径的过程，设 fuf_u 表示从 uu 往下的子树最长链，gug_u 表示和 fuf_u 不在一个子树的最长链，则树的直径是 max⁡u=1n{fu+gu}\max \limits_{u=1}^n \{f_u + g_u\}。
关键观察是，如果某次树的直径是 (u,v)(u,v)，那么路径 (lca⁡(u,v),root)(\operatorname{lca}(u,v),\text{root}) 的有效长度一定不超过 (u,v)(u,v)（有效指的是从 lca 向上遇到第一个已经删掉的点就退出）。这就意味着暴力更改路径 (lca⁡(u,v),root)(\operatorname{lca}(u,v),\text{root}) 的有效部分的复杂度仍然是均摊线性的。
于是做法就很简单了：对于每个节点 uu 用 std::set 存储其每个儿子子树的最长链即可维护 fu,guf_u,g_u，全局维护一个堆存储所有点的 fu,guf_u,g_u 信息。每次找到一条直径 (u,v)(u,v) 时，暴力修改路径 (u,v)(u,v) 和 (lca⁡(u,v),root)(\operatorname{lca}(u,v),\text{root}) 的有效部分。修改总次数为 O(n)\mathcal O(n)，因此总复杂度为 O(nlog⁡n)\mathcal O(n \log n)。
CPP
#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();
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...