Codeforces 1632 E2. Distance Tree (hard version) —

Codeforces 1632 E2. Distance Tree (hard version) —— 思维，有丶东西

本文主要是介绍Codeforces 1632 E2. Distance Tree (hard version) —— 思维，有丶东西，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一棵树，每条边权为1，f(x)表示点x到1的路径上权重和。
你可以增加一条边权为k的边，使得f(x)最大值最小。问你k在[1,n]时最大f(x)最小是多少。

题解：

我想着只搜一次，搜的时候维护上面距离当前点最远的点的距离。我感觉可以是树链剖分或者动态开点线段树，然后加一些骚操作，但是好累啊，想想都绝望，写写200行打底。
于是放弃了，还是看题解去。毕竟有段时间没打了，这个思维有时候跟不上，想这个题的时候并不能很快地想通，后面还是多做做水题锻炼思维吧。

假设我们现在答案的权重为x，如果没有新连边的话，设dep[i]是点i的深度，dep[i]<=x的这些点能够覆盖到，但是dep[i]>x的这些不行（这好像是句废话），那么对于dep[i]>x的这些点我们加一条边上使得全部能够覆盖到，最优的解法是什么？当然是距离最远的两个点的路径上最中间的位置和1连边啊，这样如果这两个最远的点a,b能够覆盖到，其它未覆盖到的点都能被覆盖到了。但是当然不能每次都找未覆盖到的点的最远距离，我们需要预处理出来。
mx[i]表示深度>=i的点中，两个点的最远距离是多少。
那么在dfs的时候我们只需要维护子树的最大距离和第二大距离即可。
mx[m2]=max(mx[m2],m1+m2-2*dep[x]);
就维护在深度为m2(m2<=m1)的时候的最远距离，为什么不是赋值到m1上？因为如果你答案能覆盖到m2了，m2和m1之间的最远关系也就消失了，我们需要找未覆盖到的最远点。
最后从后往前for一下将更深的点的答案往前传递即可。
然后找答案时怎么找？假设当前的权重为ans，那么只需要满足：未被覆盖到的点中距离最远的两个点的距离（也就是mx[ans+1]），它们的一半（(mx[ans+1]+1>>1)）+k要能够被覆盖到（也就是<=ans）即可。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int dep[N],mx[N],low;
vector<int>son[N];
int dfs(int x,int fa){dep[x]=dep[fa]+1;low=dep[x]>dep[low]?x:low;int m1=dep[x],m2=dep[x];for(int ne:son[x]){if(ne==fa)continue;int mm=dfs(ne,x);if(mm>m1)m2=m1,m1=mm;else if(mm>m2)m2=mm;}mx[m2]=max(mx[m2],m1+m2-2*dep[x]);
}
int main()
{int t;scanf("%d",&t);dep[0]=-1;while(t--){int n,x,y;scanf("%d",&n);for(int i=1;i<=n;i++)son[i].clear(),mx[i]=0;for(int i=1;i<n;i++)scanf("%d%d",&x,&y),son[x].push_back(y),son[y].push_back(x);low=0;dfs(1,0);for(int i=dep[low]-1;i;i--)mx[i]=max(mx[i],mx[i+1]);int ans=1;for(int i=1;i<=n;i++){while(ans<dep[low] && (mx[ans+1]+1>>1)+i>ans)ans++;printf("%d ",ans);}printf("\n");}return 0;
}