$2次dfs求树的直径$
$1. 任选一个起始节点开始dfs或bfs,直到到达距离它最远的节点maxu;$
$2.从maxu再次开始dfs或bfs,直到到达距离maxu最远距离的点p$
$3.maxu到p的路径就是树的直径$
$任何一颗树都是二分图$
$所以有以上性质$
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n ;
int w[N] , e[N] , ne[N] , h[N] , idx ;
int maxu , maxd ;
void add(int a , int b , int c )
{
e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++ ;
}
void dfs(int u , int fa , int d)
{
for(int i = h[u] ; i != -1 ; i = ne[i])
{
int j = e[i] ;
int k = w[i] ;
if(j == fa) continue ;
if(maxd < d + k)
{
maxd = d + k ;
maxu = j ;
}
dfs(j,u,d + k);
}
}
int main()
{
cin >> n ;
memset(h,-1,sizeof h);
int k = n - 1 ;
while(k--)
{
int a , b , c ;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs(1,-1,0);
dfs(maxu,-1,0);
cout << maxd * 10 + (maxd + 1ll) * maxd / 2 << endl ;
return 0;
}
我去,这思路也太牛逼了把,这咋想到的
为什么开十的五次方会不对,求大佬解答
因为是无向图,边是双向的,相当于逻辑上一条边实际要花费两个空间,1e5存不下,2e5可以
如果函数实现求以u为根节点的所有子链, 选出最长和次长的链相加, 作为备选答案, 并从根节点开始递归, 这样正确性不能保证吗
其中Max1, Max2分别维护的是最长/次长链的长度. 返回以该节点为跟的最长子链长度
调用dfs(1) //题目已知1为根节点.
这样总会遍历所有的点啊(因为是连通图)…
求助各位大佬, 样例过了10/12
解决了。。。
最大值维护的有问题hh
没有注释不知道数组是啥意思。
领接表存图
父节点的意思是不是收过的不重复搜索了
对 只从树的根节点往下搜索
为什么用1ll? 把1ll换成普通的1会错的
maxd是int maxd + 1ll会转成 long long 类型 就不会爆int了
if(j == fa) continue ,如果是父节点会有什么影响
是父节点不代表搜过了然后又回头了,这样不就重复计算了
maxu到p的路径,p不是距离吗?
p是到maxu最远距离的点 多谢指正 已经修正
fa是什么
u的父亲节点
谢谢,我明白了,也可以用st数组标记是不
你可以开一个数组记录这个节点的父亲节点 然后在判断这个点的父亲节点是不是j
但是你可以一个变量解决的话没必要在开数组 当然都可以