树的最长路径
题目描述
样例解释
前置知识
树的直径，又称
树的最长链
，定义为一棵树上
最远的两个节点的路径
，即树上一条不重复经过某一条边的最长的路径。树的直径也可以代指这条路径的长度。
求树的直径有两种比较常用的方法：树形DP和搜索。
如何找树的直径呢？
- 任取一点作为起点，找到距离该点最远的一个点u。 这一步可以用DFS或者BFS来解决。
- 再找到距离点u最远的一个点v。这一步可以用DFS或者BFS来解决。
- 那么点u到点v之间的路径就是一条直径了。
如何证明点u到点v之间的路径就是一条直径了呢？
要想证明点u到点v之间就是一条直径，得证明出从点u出发到达点v得路径是最长。
核心思路
-
任取一点u，从点u向下搜索，返回时搜集
边的权值
，记录两条路径： - d1：记录从点u向下走的最长路径的长度
- d2：记录从点u向下走的次长路径的长度
-
d[
u
]
=
d
1
+
d
2
d[u]=d1+d2
d
[
u
]
=
d
1
+
d
2
：表示
悬挂在点u上
的最长路径的长度，也就是穿过点u的最长路径的长度。 -
因为点u是任取的，所以遍历完树中的所有节点后，会得到一组
d[
i
]
d[i]
d
[
i
]
，答案就是
an
s
=
m
a
x
(
d
[
i
]
)
ans=max(d[i])
a
n
s
=
m
a
x
(
d
[
i
]
)
。 -
但是我们可以不需要开
d[
i
]
d[i]
d
[
i
]
数组，只要我们每次遍历完一个节点，及时更新全局变量ans即可，即
an
s
=
m
a
x
(
a
n
s
,
d
1
+
d
2
)
ans=max(ans,d1+d2)
a
n
s
=
m
a
x
(
a
n
s
,
d
1
+
d
2
)
。 -
从整棵树的根节点出发，从父节点依次到叶子节点，再从叶子节点回到父节点，最终回到整棵树的根节点。总是在返回时收集子树的信息(这里是边的权值)，从小到大更新每个节点的信息d[u]，更新最大值。这就是在树上做DP。
以节点1作为根节点，得到的搜索过程如下：
以节点2为根节点，得到搜索过程如下：
如何理解开的bool st数组呢？
为什么dfs函数的返回类型是int，但是我们在主函数中并没有设置变量来接收这个返回值呢？
因为dfs函数它的返回值是d1，含义是返回从节点u往下走的最大长度，但是d1并不是我们想要求的树的最长路径的长度，ans才是我们想要求的，并且我们在dfs函数也已经求出来了。所以我们并不需要d1的值，也就不需要设置变量来接收dfs的返回值啦。当然如果你想设置变量来接收也可以，只不过它的返回值是d1而不是说ans。
代码
写法1
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010,M=N*2;
int n;
int h[N],e[M],ne[M],w[M],idx;
bool st[N]; //标记点是否被搜过,防止向上搜索
int ans;//记录树的最长路径的长度。
//邻接表存边
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
//由于我们需要记录的是从u这个点向下搜的最长路径,比如u->x->v,权值为4,8,那么为4+8=12
//但是由于无向边被我们看做是方向相反的两条有向边,回溯时有可能把从下到上的那种有向边的权值都算进去了
//即4+8+8+4=24,但是我们只需要记录从上到下的路径长度,不需要回溯时的长度,所以,我们要开一个bool数组
//来记录节点是否已经被遍历过了,这样再回溯时就不会加上那种从下往上的有向边的权值了。
st[u]=true;//标记u这个点已经被搜过了,防止往上搜
int d1=0; //记录从u节点往下走的最大长度
int d2=0; //记录从u节点往下走的次大长度
for(int i=h[u];~i;i=ne[i]) //i是边的编号
{
int j=e[i]; //j是u的邻接点
//如果j这个点已经被遍历过了,则跳过,避免向上查找
//有可能j是u的父节点,那么j也是u的邻接点,但是由于我们是记录从上往下的路径长度,所以不能
//又回去遍历上面的,这样就又重复记录权值了
if(st[j])
continue;
//d是记录从节点u经过节点j往下走的最大长度
int d=dfs(j)+w[i];
//如果d的长度大于等于d1的长度
if(d>=d1)
{
d2=d1;//要先把原来的最大长度传给次大长度,更新现在新的次大长度
d1=d;//更新现在新的最大长度
}
//否则如果d的长度大于d2的长度(也可以写成大于等于),则只能更新次大长度
//注意这里要写成else if 而不能写成if 因为首先最大长度d1肯定是大于次大长度d2的
//如果d>=d1,则说明d>d2,如果写成if,那么可以进入第一个if语句,还能进入第二个if语句,又更新了d2,这样就错了
else if(d>d2)
d2=d; //更新次大长度
}
ans=max(ans,d1+d2); //更新答案
return d1; //返回从节点u往下走的最大长度
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d",&n);
//树有n个节点，则有n-1条边
for(int i=0;i<n-1;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
//把无向边看做是方向相反的两个有向边
add(a,b,c);
add(b,a,c);
}
//任取一个节点开始深搜
dfs(1);
printf("%d\n",ans);
return 0;
}
写法2
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010,M=N*2;
int n;
int h[N],e[M],ne[M],w[M],idx;
int ans;//记录树的最长路径的长度。
//邻接表存边
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
//father是节点u的父节点
int dfs(int u,int father)
{
//由于我们需要记录的是从u这个点向下搜的最长路径,比如u->x->v,权值为4,8,那么为4+8=12
//但是由于无向边被我们看做是方向相反的两条有向边,回溯时有可能把从下到上的那种有向边的权值都算进去了
//即4+8+8+4=24,但是我们只需要记录从上到下的路径长度,不需要回溯时的长度,所以,我们要开一个bool数组
//来记录节点是否已经被遍历过了,这样再回溯时就不会加上那种从下往上的有向边的权值了。
int d1=0; //记录从u节点往下走的最大长度
int d2=0; //记录从u节点往下走的次大长度
for(int i=h[u];~i;i=ne[i]) //i是边的编号
{
int j=e[i]; //j是u的邻接点
//如果j这个点已经被遍历过了,则跳过,避免向上查找
//有可能j是u的父节点,那么j也是u的邻接点,但是由于我们是记录从上往下的路径长度,所以不能
//又回去遍历上面的,这样就又重复记录权值了
if(j==father)
continue;
//d是记录从节点u经过节点j往下走的最大长度
int d=dfs(j,u)+w[i];
//如果d的长度大于等于d1的长度
if(d>=d1)
{
d2=d1;//要先把原来的最大长度传给次大长度,更新现在新的次大长度
d1=d;//更新现在新的最大长度
}
//否则如果d的长度大于d2的长度(也可以写成大于等于),则只能更新次大长度
//注意这里要写成else if 而不能写成if 因为首先最大长度d1肯定是大于次大长度d2的
//如果d>=d1,则说明d>d2,如果写成if,那么可以进入第一个if语句,还能进入第二个if语句,又更新了d2,这样就错了
else if(d>d2)
d2=d; //更新次大长度
}
ans=max(ans,d1+d2); //更新答案
return d1; //返回从节点u往下走的最大长度
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d",&n);
//树有n个节点，则有n-1条边
for(int i=0;i<n-1;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
//把无向边看做是方向相反的两个有向边
add(a,b,c);
add(b,a,c);
}
//任取一个节点开始深搜 同时记录某个节点它的父节点
dfs(1,-1);
printf("%d\n",ans);
return 0;
}