SDOI2013直径（树的直径）
题目描述：
题目大意：
就是在一个树上找其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。
题解：
首先，第一问很好求，两边dfs就行了，第一次从任一点找距它最远的点，再从这个点找距它的最远点，后两个点就是树的直径的两个端点，证明就不赘述了，有兴趣可以自己证一证玩一玩。
那第二问怎么办呢？假设我们有这样一个图（如下）
如图所示，中间那根直的就是树的直径之一，旁边标红的也是树的直径。（图画的不好，感性理解）
我们要知道，树的直径是必定会有交叉的，可以画个图自己看一下。
所以就会有一个想法：首先找出一条直径的起点，向终点推，如果碰到交叉，就看这个交叉是否是直径，如果是，就把第一个直径收缩，再继续找。再从终点向起点收缩一遍。
最后就是代码实现了，收缩的过程是真滴玄学。
代码如下：
#include<iostream>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define rint register int
#define M 200005
using namespace std;
inline int read()
{
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*f;
}
inline ll max(ll a,ll b){return a>b?a:b;}
ll dis[M],maxx,s,t;
ll n,m,cnt,head[M],vis[M];
ll dep[M],father[M],l,r,ans,son[M];
struct edge
{
int to,nex,v;
}e[M<<1];
inline void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].v=w;
e[cnt].nex=head[u];
head[u]=cnt;
}
void dfs(int u,int fa)
{
for(rint i=head[u];i;i=e[i].nex)
{
int v=e[i].to;if(v==fa) continue;father[v]=u;
dis[v]=dis[u]+e[i].v;dfs(v,u);
}
}
void find(int u,int fa)
{
dep[u]=0;ll maxn=0;
for(rint i=head[u];i;i=e[i].nex)
{
int v=e[i].to;if(v==father[u] || vis[v]==1) continue;
find(v,u);maxn=max(maxn,dep[v]+e[i].v);
}
dep[u]=maxn;
}
int main()
{
n=read();
for(rint i=1;i<=n-1;++i)
{
int x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
dfs(1,0);
for(rint i=1;i<=n;++i)
{
if(dis[i]>maxx) maxx=dis[i],s=i;
dis[i]=0;
}
dfs(s,0);maxx=0;
for(rint i=1;i<=n;++i)
{
if(dis[i]>maxx) maxx=dis[i],t=i;
}
printf("%lld\n",maxx);
int l=t,r=s,now=t;
while(now!=s)
{
vis[now]=1;
son[father[now]]=now;
now=father[now];
}
now=t;
while(now!=s)
{
dep[now]=0;
find(now,0);
if(dep[now]==maxx-dis[now]) l=now;
now=father[now];
}
now=s;
while(now)
{
find(now,0);
if(dep[now]==dis[now]) r=now;
now=son[now];
}
while(l!=r && l)
{
l=father[l];
++ans;
}
printf("%lld\n",ans);
return 0;
}
View Code
谢谢大家！
版权声明：本文为mxrmxr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。