树的最长路径
题目
思路
这道题的前置知识点可以参考[树的最长路径](1072. 树的最长路径 - AcWing题库)easy版，核心代码如下：
void up(int u,int fa){
st[u]=1;
for(auto v:e[u]){
if(v.to==fa) continue;
up(v.to,u);
if(f[u][1]<=f[v.to][1]+v.w){
f[u][2]=f[u][1];
f[u][1]=f[v.to][1]+v.w;
}
else if(f[u][2]<=f[v.to][1]+v.w){
f[u][2]=f[v.to][1]+v.w;
}
}
}
以某点为根的子树的最长路径即为以该点为根的最长路与次长路的长度和，一遍dfs即可求出所有子树的最长路径，但在这个题里，显然某点的最长路径不一定存在于某点的子树中，而存在于该点的根节点里面，这个时候就需要引入换根的概念了
如图给出了一颗树，当以1为根时，显然他的最长直径为路径1-3-7-11（f[1] [2]=3,一维表示以1为根，二维表示第2长的路）与路径1-4-9-13-15（f[1] [1]=4）的长度和7.
但当我们考虑结点4时,第一遍dfs跑出来的结果p[4] [1]=3,p[4] [2]=2,显然不是最优的，因为把结点1看作他的子节点时，f[4] [1]可以被f[1] [2]+1替换，同理f[3] [1]可以被f[1] [1]+1替换，f[3] [2]继承 f[3] [1]。
如果此时我们对每个节点都跑一遍dfs的话可以解决这个问题，但其时间复杂度为O(n^2) 的，显然不符合题面的要求，所有需要考虑怎么在O(n)的时间复杂度下得出每点的答案，这个时候对每个结点观察可以看出，答案是否需要更新只和他的根节点信息有关，当根节点长度大于p[i][1]或者p[i][2]时按需求更新答案即可。
具体的更新答案的情况有两类，一种是子节点v被父节点u的第一长路径覆盖，另一种则是被第二长路径覆盖或不被覆盖。
当我们考虑第一种情况是，对应图中的v=4号结点，当前结点v被根节点u的第一长的路径包括在内，v的第一长的路径长度一定是最优的，但需要考虑f[v] [2]与f[u] [2]+1的关系。第二种情况对应v=2或者v=3，此时根节点u中一定存在一条最优的路径大于p[v] [1]与p[v] [2]，因为根结点在寻找最长路径时没有考虑经过子节点v，所以子节点v中的任何路径都是非最优解，那么直接将p[v] [2]更新为p[v] [1],并用p[u] [1]+1替换p[v] [1]。
注意在每一次更新都要维护当前的结点所选的每一条路都要经过的那个子节点，用来后续判断某个点是否为父节点所选
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 10;
typedef pair<int,int> PII;
bool st[N];
struct tree{
int to;
};
int size[N],f[N][3],p[N][3];
vector<tree> e[N];
void up(int u){
st[u]=1;
for(auto v:e[u]){
if(st[v.to]) continue;
up(v.to);
if(f[u][1]<f[v.to][1]+1){
f[u][2]=f[u][1];
p[u][2]=p[u][1];
f[u][1]=f[v.to][1]+1;
p[u][1]=v.to;
}
else if(f[u][2]<f[v.to][1]+1){
f[u][2]=f[v.to][1]+1;
p[u][2]=v.to;
}
}
}
void down(int u){
st[u]=1;
for(auto v:e[u]){
if(st[v.to]) continue;
if(p[u][1]==v.to){
if(f[v.to][1]<f[u][2]+1){
f[v.to][2]=f[v.to][1];
p[v.to][2]=p[v.to][1];
f[v.to][1]=f[u][2]+1;
p[v.to][1]=u;
}
else if(f[v.to][2]<f[u][2]+1){
f[v.to][2]=f[u][2]+1;
p[v.to][2]=u;
}
}
else{
f[v.to][2]=f[v.to][1];
p[v.to][2]=p[v.to][1];
f[v.to][1]=f[u][1]+1;
p[v.to][1]=u;
}
down(v.to);
}
}
void solve(){
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back({v});
e[v].push_back({u});
}
up(1);
for(int i=1;i<=n;i++) st[i]=0;
down(1);
int ans=0;
for(int i=1;i<=n;i++){
cout<<f[i][1]+f[i][2]<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin >> t;
while (t--) {
solve();
}
}