CF911F Tree Destruction(树的直径）

Problem - F - Codeforces

题意：

给一棵树，每次加上两个叶节点的距离并删除其中一个叶节点，问最大总距离和是多少。

题解：

叶节点的最大距离肯定是直径两端的距离；那么直径之外的点与其他节点的最远距离肯定在直径的某一端。那么我们首先把直径和其两端点求出来，再加上此节点到那个端点的距离；这个距离可用两个dfs 求直径端点时顺便求出；再考虑直径上的点，每次删掉一端的点就好了，sum+=;

/*keep on going and never give up*/#includeusing namespace std;#define int long long#define LL long long#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const double E = exp(1);const double PI = acos(-1.0);const int maxn=4e5+10;const int Mod=1e9+7;const int maxn = 2e5+10;struct answer{   int u,v;}a[maxn];vector G[maxn];bool v[maxn];int d[maxn],pre[maxn];int n,tot;int root,leaf;LL ans;void dfs(int u, int fa){    d[u] = d[fa]+1;    pre[u] = fa;//统计距离；    for (int i=0; i<G[u].size(); i++) if (G[u][i]!=fa) dfs(G[u][i],u);} void Find(int x, int df, int dr, bool flag = 1){    for (int i=0; idr) {     a[tot].u = leaf;     a[tot].v = x;     ans += df; } else {     a[tot].u = root;     a[tot].v = x;     ans += dr; } tot++;    }} int main(){    scanf("%d",&n);for (int i=1; i<=n; i++) G[i].clear();tot = 0;int u,v;for (int i=1; i<n; i++) {   scanf("%d %d",&u,&v);   G[u].push_back(v);   G[v].push_back(u);}   ans = 0; d[0] = 0; root = 1; dfs(root,0); for (int i=1; i<=n; i++) if (d[root]<d[i]) root = i; leaf = 1; dfs(root,0);//两遍dfs找到root和leaf； for (int i=1; i<=n; i++) if (d[leaf]<d[i]) leaf = i; memset(v,0,sizeof(v)); int x = leaf; while (1){     v[x] = 1;     Find(x,d[leaf]-d[x],d[x]-1,0);     if (x == root) break;     x = pre[x]; }  x = leaf; while (x!=root) {     a[tot].u = root; a[tot].v = x; tot++;     ans += d[x]-1;     x = pre[x]; }  printf("%I64d\n",ans); for (int i=0; i<tot; i++) printf("%d %d %d\n",a[i].u,a[i].v,a[i].v);}

ps：硬干2400的题真是太有意思了QwQ