题解 SP1437 【PT07Z - Longest path in a tree】

参考 OIwiki，【树的直径】模板题。图中所有最短路径的最大值即为【直径】，可以用两次 DFS 或树形 DP 在 $O(n)$ 内求出。 ## 题目大意 给定一个无权无向的树。编写程序以输出该树中最长路径（从一个节点到另一个节点）的长度。在这种情况下，路径的长度是我们从开始到目的地的遍历边数。 ## 大体思路 ### 一、两次 $\mathbb{DFS}$ 首先对任意一个结点做 DFS 求出最远的结点，然后以这个结点为根结点再做 DFS 到达另一个最远结点。第一次 DFS 到达的结点可以证明一定是这个图的直径的一端，第二次 DFS 就会达到另一端。下面来证明这个定理。 但是在证明定义之前，先证明一个引理： 引理：在一个连通无向无环图中，$x$、$y$ 和 $z$ 是三个不同的结点。当 $x$ 到 $y$ 的最短路与 $y$ 到 $z$ 的最短路不重合时，$x$ 到 $z$ 的最短路就是这两条最短路的拼接。 证明：假设 $x$ 到 $z$ 有一条不经过 $y$ 的更短路 $\delta(x,z)$ ，则该路与 $\delta(x,y)$、$\delta(y,z)$ 形成一个环，与前提矛盾。 定理：在一个连通无向无环图中，以任意结点出发所能到达的最远结点，一定是该图直径的端点之一。 证明：假设这条直径是 $\delta(s,t)$ 。分两种情况： - 当出发结点 $y$ 在 $\delta(s,t)$ 时，假设到达的最远结点 $z$ 不是 $s,t$ 中的任一个。这时将 $\delta(y,z)$ 与不与之重合的 $\delta(y,s)$ 拼接（也可以假设不与之重合的是直径的另一个方向），可以得到一条更长的直径，与前提矛盾。 - 当出发结点 $y$ 不在 $\delta(s,t)$ 上时，分两种情况： - 当 $y$ 到达的最远结点 $z$ 横穿 $\delta(s,t)$ 时，记与之相交的结点为 $x$。此时有 $\delta(y,z)=\delta(y,x)+\delta(x,z)$。而此时 $\delta(y,z)>\delta(y,t)$ ，故可得 $\delta(x,z)>\delta(x,t)$ 。由 1 的结论可知该假设不成立。 - 当 $y$ 到达的最远结点 $z$ 与 $\delta(s,t)$ 不相交时，记 $y$ 到 $t$ 的最短路首先与 $\delta(s,t)$ 相交的结点是 $x$。由假设 $\delta(y,x)>\delta(y,x)+\delta(x,t)$。而 $\delta(y,z)+\delta(y,x)+\delta(x,s)$ 又可以形成 $\delta(z,s)$，而 $\delta(z,s)>\delta(x,s)+\delta(x,t)+2\delta(y,x)=\delta(s,t)+2\delta(y,x)$，与题意矛盾。 ### 二、树形 $\mathbb{DP}$ 一棵有根树的最长链，可能出现以下两种情况：  因此，对于每个节点，记录两个值：$d_1$ 表示以该节点为根的子树中，根节点到叶子节点的距离最大值，$d_2$ 表示上述的非严格次大值。 通过 dfs 更新 $d_1,d_2$ 即可直径就是 $\max\{d_1+d_2\}$。 ## 完整代码 (方法二) ```cpp #include<bits/stdc++.h> using namespace std; #define rep(ii,aa,bb) for(re int ii=aa;ii<=bb;ii++) #define Rep(ii,aa,bb) for(re int ii=aa;ii>=bb;ii--) typedef long long ll; typedef unsigned long long ull; const int maxn=1e5+5;//个人习惯 namespace IO_ReadWrite{ #define re register #define gg getchar() template <typename T> inline void read(T &x){ x=0;re T f=1;re char c=gg; while(c>57||c<48){if(c=='-') f=-1;c=gg;} while(c>=48&&c<=57){x=(x<<1)+(x<<3)+(c^48);c=gg;} x*=f;return; } inline void ReadChar(char &c){ c=gg; while(!isalpha(c)) c=gg; } template <typename T> inline void write(T x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar('0'+x%10); } template <typename T> inline void writeln(T x){write(x);putchar('\n');} } using namespace IO_ReadWrite;//快读 vector<int> e[maxn];//代替邻接表存树 int n,d; inline int dfs(int u,int p) { int d1=0,d2=0;//记录最大值和次大值 for(re int i=0;i<e[u].size();i++) { int v=e[u][i]; if(v==p) continue; int d_new=dfs(v,u)+1;//基础树形dfs if(d_new>d1) d2=d1,d1=d_new; else if(d_new>d2) d2=d_new;//更新 } d=max(d,d1+d2);//取最大值 return d1; } int main() { read(n); rep(i,1,n-1){ int a,b; read(a);read(b); e[a].push_back(b); e[b].push_back(a);//存树 } dfs(1,-1);//将无根树换成有根树，假设 fa[1]=-1 write(d);//输出 return 0;//完美 } ```