CF911F Tree Destruction 题解

题意：

给定一棵 $n(2\le n \le 2\times 10^5)$ 个结点的无根树。

每次挑选这棵树的两个叶子，加上两个叶子之间的边数（距离），然后将其中一个点去掉。

问你重复操作后边数（距离）之和最大可以是多少？

很有趣的贪心题，并且需要一定代码能力。

尝试一下用Roundgod刚刚教我的方法来做这道题

注：刚刚请教了Roundgod有关贪心题的做法

他说思想是可以考虑两个元素，谁会被优先选。

正好这是一道比较简单的贪心题，可以试一试。

对于两个不同的叶子 $j,k$ ，如果已经确定了 $j$ ，怎么找到最优的 $k$ ？

这里需要一个结论：无权树上任意一个结点，与它距离最远的结点一定是直径的某个端点。

那么确定了 $j$ 以后， $k$ 一定是选择直径端点中较远的那一个。

不同的 $j$ 对应的 $k$ 不一定相同，因此考虑 $k$ 相同时，我们会选哪个 $j$

如果 $j_1,j_2$ 都是非直径端点的叶子

那无所谓顺序，直接一个个删然后加上贡献就好了
如果 $j_1,j_2$ 中有一个是直径端点

我们一定会选择非直径端点的去删，不然 $k$ 不同的结点贡献就会无辜变少。

也就是为了维持直径端点的贡献，我们选择最后没叶子的时候再删除它们

然后我们就把非直径的点都删完了。最后直径上的就可以一个个删了。

感觉代码写起来有一定难度。

首先 $2$ 遍dfs找出直径的两个端点 $x,y$ ，

接着从 $x$ 出发跑一遍dfs，递归地找到深度最大的那个儿子，它就是直径上的下一个点

这样就标记了所有直径上的点

然后我们再从 $x$ 出发跑一遍dfs计算非直径结点的贡献，过程中记录那些非直径结点和直径端点的lca（代码中的 rt ）

最后直接跳直径算贡献就好了。

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(2e5+15))
#define F first
#define S second

bitset<N> on;
vector< pair<int,int> >c;
int n,x,y,res,pos=1,head[N],d[N],fa[N];
struct Edge{int u,v,next;} e[N*2];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void dfs1(int u)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(~d[v]) continue;
        d[v] = d[u] + 1; dfs1(v);
    }
}
void dfs2(int u)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(d[v] > d[u])
        {
            fa[v] = u; dfs2(v);
            on[u] = on[u] | on[v];
        }
    }
}
void dfs3(int u,int rt)
{
    for(int i=head[u],v; i; i=e[i].next)
        if(d[v=e[i].v] > d[u]) dfs3(v, on[v] ? v : rt);
    if(!on[u])
    {
        // d(x->u) > d(y->u) 
        if(d[u] > d[u] + d[y] - d[rt]*2)
        {
            res += d[u];
            c.push_back({x,u});
        }else
        {
            res += d[u] + d[y] - d[rt]*2;
            c.push_back({y,u});
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    // -----------find-----------
    memset(d,-1,sizeof(d)); d[1]=0; dfs1(1);
    for(int i=1; i<=n; i++) if(d[x] < d[i]) x=i;
    memset(d,-1,sizeof(d)); d[x]=0; dfs1(x);
    for(int i=1; i<=n; i++) if(d[y] < d[i]) y=i;
    // -----------proc-----------
    on[y]=1; dfs2(x); dfs3(x,x);
    for(; x!=y; y=fa[y]) res += d[y], c.push_back({x,y});
    cout << res << '\n';
    for(auto i : c) cout << i.F << ' ' << i.S << ' ' << i.S << '\n';
    return 0;
}