小Q最近学习了一些图论知识。
根据课本,有如下定义。树:无回路且连通的无向图,每条边都有正整数的权值来表示其长度。如果一棵树有N个节点,
可以证明其有且仅有N-1 条边。
路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点a和点b的路径上各边长度之和。
称dis(a,b)为a、b两个节点间的距离。
直径:一棵树上,最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道,对于给定的一棵树,其直径的长度是多少,以及有多少条边满足所有的直径都经过该边。
Input
第一行包含一个整数N,表示节点数。
接下来N-1行,每行三个整数a, b, c ,表示点 a和点b之间有一条长度为c的无向边。
2≤N≤200000,所有点的编号都在1..N的范围内,
边的权值≤10^9。
Output
共两行。第一行一个整数,表示直径的长度。第二行一个整数,表示被所有
直径经过的边的数量。
Sample Input
6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100
Sample Output
1110
2
【样例说明】
直径共有两条,3 到2的路径和3到6的路径。这两条直径都经过边(3, 1)和边(1, 4)。
/* 从1出发找一个离1最远的a 再从a出发,找出所有点到a的距离,求出最长的那个距离,对应点为b 则a...................b为直径 | | L R 设i为b的父亲点,形如 a................i..b | | L R 如果i到以其为根的子树的最大距离w=dis(a,i) 则说明i到b这一条边不是所有直径都要走的边 同理枚举a的子结点i,形如 a..i................b | | L R 如果i到以其为根的子树的最大距离w=dis(i,b) 则说明a到i这一条边不是所有直径都要走的边 */ #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; typedef long long LL; const int maxn=200005; int n,u,v,w,np=0,first[maxn],fa[maxn],son[maxn],vis[maxn],a,b,cnt=0; LL dist[maxn]; struct edge { int to,next,w; }e[2*maxn]; void addedge(int u,int v,int w) { e[++np]=(edge){v,first[u],w}; first[u]=np; } void dfs(int i,int f,LL dis,int &x) { dist[i]=dis; fa[i]=f; if(dist[x]<dis) x=i; for(int p=first[i];p;p=e[p].next) { int j=e[p].to; if(j==f) continue; dfs(j,i,dis+e[p].w,x); } } int dfs1(int i,int f,int d) { int t=d; for(int p=first[i];p;p=e[p].next) { int j=e[p].to; if(j==f || vis[j]) continue; t=max(t,dfs1(j,i,d+e[p].w)); } return t; } void solve() { cout<<dist[b]<<endl; for(int j=b;j;j=fa[j]) vis[j]=1,son[fa[j]]=j;//找出直径上的点 int i=fa[b],L=a,R=b; while(i) { w=dfs1(i,0,0); //从i点出发,找另一条路,不能经过直径上的边 if(w==dist[i]) { R=i; break; } i=fa[i]; } i=son[a]; while(i) { w=dfs1(i,0,0); if(w==dist[b]-dist[i]) { L=i; break; } i=son[i]; } for(int i=L;i!=R;i=fa[i]) cnt++; printf("%d\n",cnt); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs(1,0,0,a=0);//采用两次dfs的方式求出直径 dfs(a,0,0,b=0); solve(); return 0; }