[文章目录]
Description
小Q最近学习了一些图论知识。根据课本，有如下定义。树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。如果一棵树有N个节点，可以证明其有且仅有N-1 条边。 路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b)
表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。
直径：一棵树上，最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道，对于给定的一棵树，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。
神题啊，卡死我了。。。原来想当水题切的，越写越乱。更博只是想说两条性质。
1.所有直径都过的边一定是连在一起的。
2.直径们一定是类似左面一个大根，中间一条链，右面一条大根。或是可能没有链，直接一个大菊花的形状。
还有一点，直径求法不只有树形DP。dfs*2也挺好
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,start,tar,fna;
int path[201000];
int head[201000],to[401000],nxt[401000],data[401000],cnt;
ll dis[201000],ans;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
}
void dfs(int x,int pre,ll deep)
{
if(deep>ans) ans=deep,tar=x;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre)
dfs(to[i],x,deep+data[i]);
}
bool dfs_flag(int x,int pre,ll deep)
{
if(x==tar) {path[tar]=-1; dis[tar]=deep; return true;}
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre&&dfs_flag(to[i],x,deep+data[i]))
{path[x]=to[i],dis[x]=deep; return true;}
return false;
}
ll dfs_len(int x,int pre)
{
ll mx=0;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre&&!path[to[i]])
mx=max(mx,dfs_len(to[i],x)+data[i]);
return mx;
}
int main()
{
scanf("%d",&n);
for(int x,y,z,i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1,0,0);
start=tar; ans=0;
dfs(start,0,0);
dfs_flag(start,0,0);
ll now=0;
int l=start,r=tar;
for(int i=start;i!=tar;i=path[i])
{
ll tmp=dfs_len(i,0);
if(tmp==dis[i]) l=i;
if(tmp==ans-dis[i]) {r=i; break;}
}
for(int i=l;i!=r;i=path[i]) fna++;
printf("%lld\n%d",ans,fna);
return 0;
}