Written with StackEdit.
Description
小(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) 的无向边。
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))。
HINT
对于(100\%)的测试数据：(2≤N≤2*10^5)，所有点的编号都在(1..N)的范围内， 边的权值(≤10^9)。
Solution
- 第一问显然,两次(dfs)即可.
- 关于第二问,各个最远点的(LCA)一定是在所有直径上的.
- 所以两次(dfs)时记录所有的最远点,求出它们的(LCA)
(熟练剖腹),两个(LCA)的深度差即为答案(可以感性理解一下).
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int MAXN=2e5+10;
int n;
int cnt=0,head[MAXN];
int nx[MAXN<<1],to[MAXN<<1],val[MAXN<<1];
LoveLive dis[MAXN];
int dep[MAXN],siz[MAXN],top[MAXN],Fa[MAXN],sons[MAXN];
inline void add(int u,int v,int w)
{
++cnt;
nx[cnt]=head[u];
to[cnt]=v;
val[cnt]=w;
head[u]=cnt;
}
void dfs1(int u,int fa)
{
Fa[u]=fa;
siz[u]=1;
for(int i=head[u];i;i=nx[i])
{
int v=to[i];
if(v==fa)
continue;
dep[v]=dep[u]+1;
dis[v]=dis[u]+val[i];
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[sons[u]])
sons[u]=v;
}
}
void dfs2(int u,int tp,int fa)
{
top[u]=tp;
if(!sons[u])
return;
dfs2(sons[u],tp,u);
for(int i=head[u];i;i=nx[i])
{
int v=to[i];
if(v==fa || v==sons[u])
continue;
dfs2(v,v,u);
}
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=Fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void init(int rt)
{
memset(sons,0,sizeof sons);
dep[rt]=1;
dis[rt]=0;
}
vector<int> G;
int main()
{
n=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
add(u,v,w);
add(v,u,w);
}
init(1);
dfs1(1,0);
dfs2(1,1,0);
LoveLive ans=0;
for(int i=1;i<=n;++i)
{
if(dis[i]>ans)
G.clear(),ans=dis[i];
if(ans==dis[i])
G.push_back(i);
}
int now=G[0];
int tot=G.size();
for(int i=1;i<tot;++i)
now=LCA(now,G[i]);
int lca1=now;
int rt=G[0];
ans=0;
init(rt);
dfs1(rt,0);
dfs2(rt,rt,0);
G.clear();
for(int i=1;i<=n;++i)
{
if(dis[i]>ans)
G.clear(),ans=dis[i];
if(ans==dis[i])
G.push_back(i);
}
printf("%lld
",ans);
now=G[0];
tot=G.size();
for(int i=1;i<tot;++i)
now=LCA(now,G[i]);
int lca2=now;
printf("%d
",abs(dep[lca1]-dep[lca2]));
return 0;
}