换根 DP 经典模型：O(N) 求解树上经过每个节点的最长路径
题目描述
【最长路径】有一棵 n (2≤n≤100000) 个点的树，请求出经过每个点的长度最长的简单路径有多长。 定义一条路径的长度为这条路径上经过了多少条边。
输入格式第一行一个整数 n 表示点的数目。 接下来 n−1 行，每行两个整数 x,y 描述一条树边。
输出格式输出共 n 行。 第 i 行表示经过编号为 i 的点的长度最长的简单路径有多长。
样例输入
5 1 2 1 5 2 3 2 4样例输出
3 3 3 3 3一、 题目分析与物理模型建构
1. 核心题意解析给定一棵无向无权树（边长默认为 1），要求在强行规定“路径必须包含节点 i”的前提下，求出整棵树中能走出的最长简单路径长度（不能走回头路）。
2. 易混淆概念辨析：它不是单纯的“树的直径”很多初学者看到“树的最长路”，会直接联想到“树的直径”。必须明确区分：
树的直径：是整棵树的全局最长路，答案通常只有一个。
本题诉求：是求 n 个局部最优解。对于边缘节点，经过它的最长路径往往达不到整棵树的直径长度。
3. 物理模型的具象化（十字路口法则）理解这道题的突破口，在于搞懂什么是“经过节点i”。 想象你站在节点 i 这个十字路口，周围辐射出多条岔路。所谓“经过你的最长路径”，在物理形态上只有一种可能：从以你为中心的众多岔路中，挑选出最长的那两条路，拼接成一条直线。
基于这个物理直觉，我们将无根树转化为有根树。对于任意一个节点i，它向外辐射的“岔路”被严格划分为两类：
向下走：通向它的各个子树分支。
向上走：通向它的父节点，并借由父节点蔓延至其他旁系分支。
只要我们能求出节点i向下的最长路、向下的次长路（必须属于不同分支），以及向上的最长路，从中挑出最大的两个相加，就是最终答案。
二、 思考过程与解题思路（状态解耦与备胎模型）
数据规模约束：n≤10^5 意味着对每个节点分别跑 DFS 的 O(N^2) 暴力做法必定 TLE。我们必须利用相邻节点状态转移的微小差异，使用 O(N) 的二次扫描换根法。
求最长路径的核心难点在于max操作的不可逆性。 当父节点x试图将自身的“最长路径”下发给子节点v时，如果x自身的向下最长路径恰好是顺着v所在的子树延伸出来的，那么x就绝对不能把这个长度传给 v，否则会形成U型弯（走回头路）。
为了完美解决路径重合问题，我们必须在代码层面进行状态解耦，维护以下四个核心一维数组：
d1[i]：以 i 为根的子树中，从 i 向下的最长路径长度。
d2[i]：以 i 为根的子树中，从 i 向下的次长路径长度（必须与最长路不在同一个儿子的分支上）。
son1[i]：节点 i 取得向下最长路径时，所经过的直接子节点编号。
up[i]：节点 i 向父节点方向走的最长路径长度。
三、 算法设计
算法严格分为两次DFS遍历：
1. 第一次扫描：DFS1（自底向上）
目标：计算所有的 d1,d2,son1。状态转移逻辑： 遍历节点 x 的所有子节点 v，设从 v 传递上来的路径长度为 len=d1[v]+1。
若 len>d1[x]：原先的最长路退位为次长路（d2[x]=d1[x]），新的最长路更新（d1[x]=len），并记录儿子（son1[x]=v）。
若 d2[x]<len≤d1[x]：该路径足以更新次长路（d2[x]=len）。
2. 第二次扫描：DFS2（自顶向下）
目标：计算所有的up数组（换根推导）。状态转移逻辑： 父节点x在下放信息给子节点v时，必须进行判断x的向下最长路d1[x]是否经过子节点v：
如果 v==son1[x]（最长路经过了 v）：启用备胎模型，父节点只能提供向上的最长路up[x]与向下的次长路d2[x]中的较大值。即up[v]=max(up[x],d2[x])+1。
如果v!=son1[x]（最长路未经过 v）：互不干涉，父节点提供向上的最长路up[x]与向下的最长路d1[x]中的较大值。即up[v]=max(up[x],d1[x])+1。
四、 时空复杂度分析
时间复杂度：O(N)。DFS1和DFS2各自对整棵树的节点和边遍历了一次，且每次状态转移均为O(1)的操作。最后结算答案也是 O(1)。
空间复杂度：O(N)。采用了链式前向星存图，边表大小为2N；同时开辟了4个大小为 N 的一维状态数组。没有使用高维数组，空间利用率高。
五、 难点总结
逆向断流（无备胎可用）：如果在DFS1中不维护次大值d2[x]，DFS2在遇到v==son1[x]时将无合法状态可供转移，导致答案偏小。
根节点的初始化：
up[root]必须被初始化为 0，因为绝对的根节点上方没有路径。结算答案的常数优化：在合并 {d1[i],d2[i],up[i]} 时，很多初学者会将其放入数组并调用
sort排序。但实际上，根据定义 d1[i]≥d2[i] 永远成立，故 d1[i] 必为前两大值之一。答案可直接 O(1) 简化为 d1[i]+max(d2[i],up[i])，无需排序。
六、完整代码
//最长路径 #include <iostream> #include <algorithm>//对应min max #include <cstring>//对应memset using namespace std; int n;//共有n个点 int h[100010]; int vtex[200020]; int nxt[200020]; //dp[i][0]代表i的子树中到i的最长路径 dp[i][1]代表i的子树中到i的次长路径 //dp[i][0][0]代表的是i的子树中最长路径长度 //dp[i][1][0]代表的是i的子树中次长路径长度 //dp[i][0][1]代表的是i的子树中最长路径是走哪个儿子上来的 //dp[i][1][1]代表的是i的子树中次长路径是走哪个儿子上来的 int dp[100010][2][2]; int d1[100010];//代表i的子树中到i的最长路径长度 int d2[100010];//代表i的子树中到i的次长路径长度 int son1[100010];//son1[i]代表i的子树中到i的最长路径是走i的哪个儿子上来的 int son2[100010];//son2[i]代表i的子树中到i的次长路径是走i的哪个儿子上来的 int up[100010];//代表i往父节点方向走的最长路径长度 int idx; void addedge(int u,int v){ vtex[idx]=v; nxt[idx]=h[u]; h[u]=idx++; } //自底向上：收集子树内的最长和次长路径 void dfs1(int x,int fa){ int p=h[x]; while(p!=-1){ int v=vtex[p]; if(v==fa){ p=nxt[p]; continue;//防止重复访问 } dfs1(v,x); //最长和次长判断 if(d1[v]+1>d1[x]){ d2[x]=d1[x];//旧的最长变成新的次长 son2[x]=son1[x];//记录次长路的儿子 d1[x]=d1[v]+1;//更新新的最长路 son1[x]=v;//记录最长路的儿子 } else if(d1[v]+1>d2[x] && v!=son1[x]){ d2[x]=d1[v]+1; son2[x]=v; } p=nxt[p]; } } //自顶向下，换根推导向上的up数组（经典的次大值备胎模型） void dfs2(int x,int fa){ int p=h[x]; while(p!=-1){ int v=vtex[p]; if(v==fa){//避免重复访问 p=nxt[p]; continue; } // 父节点x查岗：准备把上方的最长路传给儿子 v //如果父节点的最长路没经过v，父节点放心地传 向上路 和 最长路 的最大值 if(son1[x]!=v) up[v]=max(up[x],d1[x])+1; //如果父节点的最长路正好踩在儿子v头上，父节点只能传 向上路 和 次长路 的最大值 else up[v]=max(up[x],d2[x])+1; dfs2(v,x);//子节点继续往下传 p=nxt[p]; } } int main(){ cin>>n; //初始化头指针数组为空 memset(h,-1,sizeof(h)); for(int i=1;i<n;i++){ int u,v; cin>>u>>v; addedge(u,v);//无向图双向存边 addedge(v,u); } dfs1(1,0);//第一遍扫描，定根为1，收集子树信息 up[1]=0;//根节点向上路径为0 dfs2(1,0);//自顶向下推导全局 for(int i = 1; i <= n; i++) { //由于d1[i]>=d2[i]恒成立 //故{d1[i], d2[i], up[i]}中最大的两个数之和，必为d1[i]+max(d2[i],up[i]) cout<<d1[i]+max(d2[i],up[i])<<endl; } return 0; }