SDOI2013直径（树的直径）

时间：2024-01-11 14:33:02

题目描述：

点这里

题目大意：

就是在一个树上找其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

题解：

首先，第一问很好求，两边dfs就行了，第一次从任一点找距它最远的点，再从这个点找距它的最远点，后两个点就是树的直径的两个端点，证明就不赘述了，有兴趣可以自己证一证玩一玩。

那第二问怎么办呢？假设我们有这样一个图（如下）

SDOI2013直径（树的直径）

如图所示，中间那根直的就是树的直径之一，旁边标红的也是树的直径。（图画的不好，感性理解）

我们要知道，树的直径是必定会有交叉的，可以画个图自己看一下。

所以就会有一个想法：首先找出一条直径的起点，向终点推，如果碰到交叉，就看这个交叉是否是直径，如果是，就把第一个直径收缩，再继续找。再从终点向起点收缩一遍。剩下的边就是题目中要求的了。

最后就是代码实现了，收缩的过程是真滴玄学。

代码如下：

#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=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){s=s*+ch-'';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<<];

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]=;ll maxn=;

    for(rint i=head[u];i;i=e[i].nex)

    {

        int v=e[i].to;if(v==father[u] || vis[v]==) continue;

        find(v,u);maxn=max(maxn,dep[v]+e[i].v);

    }

    dep[u]=maxn;

}

int main()

{

    n=read();

    for(rint i=;i<=n-;++i)

    {

        int x=read(),y=read(),z=read();

        add(x,y,z),add(y,x,z);

    }

    dfs(,);

    for(rint i=;i<=n;++i)

    {

        if(dis[i]>maxx) maxx=dis[i],s=i;

        dis[i]=;

    }

    dfs(s,);maxx=;

    for(rint i=;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]=;

        son[father[now]]=now;

        now=father[now];

    }

    now=t;

    while(now!=s)

    {

        dep[now]=;

        find(now,);

        if(dep[now]==maxx-dis[now]) l=now;

        now=father[now];

    }

    now=s;

    while(now)

    {

        find(now,);

        if(dep[now]==dis[now]) r=now;

        now=son[now];

    }

    while(l!=r && l)

    {

        l=father[l];

        ++ans;

    }

    printf("%lld\n",ans);

    return ;

}

谢谢大家！

相关文章