[BZOJ3124/Luogu3304][SDOI2013]直径(树的直径)

发布于 2018-05-27  137 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3124/Luogu3304][SDOI2013]直径(树的直径)

Description

小Q最近学习了一些图论知识。根据课本,有如下定义。树:无回路且连通的无向图,每条边都有正整数的权值来表示其长度。如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)
表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。
直径:一棵树上,最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道,对于给定的一棵树,其直径的长度是多少,以及有多少条边满足所有的直径都经过该边。

Tag

树的直径

解决思路

第一问可以用两次搜索求得。
考虑把第一问求出的直径截出来,这样我们就得到了若干直径中的一条。因为直径的性质保证所有的直径必交于连续一段,所以用两个指针扫。先从左往右扫描,从每一个点$BFS$找到最深的点,设这个点的深度为$deep$,若$deep$与该点右边直径部分的长度相同,则说明我们找到了一条新的直径,从这个点向右都不是必须经过的点了,找到右端点。
对于向左的也是同理,这样我们就确定了重合区间的左右端点。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
const int maxN=201000;
const int maxM=maxN*2;
const int inf=2147483647;

int n;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
ll W[maxM];
ll Dist[maxM],Sum1[maxN],Sum2[maxN];
int Queue[maxN],Fa[maxN],St[maxN];
bool vis[maxN];

void Add_Edge(int u,int v,int w);
int Bfs(int S);

int main()
{
    mem(Head,-1);
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        Add_Edge(u,v,w);
    }

    mem(vis,0);
    Bfs(1);
    int id=1;
    for (int i=2;i<=n;i++) if (Dist[i]>Dist[id]) id=i;

    mem(vis,0);
    Bfs(id);
    id=1;
    for (int i=2;i<=n;i++) if (Dist[i]>Dist[id]) id=i;
    ll Ans=Dist[id];

    int now=id,cnt=0;
    while (now) St[++cnt]=now,now=Fa[now];

    Sum1[1]=0;
    for (int i=2;i<=cnt;i++)
        for (int j=Head[St[i]];j!=-1;j=Next[j])
            if (V[j]==St[i-1]){
                Sum1[i]=Sum1[i-1]+W[j];break;
            }

    Sum2[cnt]=0;
    for (int i=cnt-1;i>=1;i--)
        for (int j=Head[St[i]];j!=-1;j=Next[j])
            if (V[j]==St[i+1]){
                Sum2[i]=Sum2[i+1]+W[j];break;
            }

    mem(vis,0);
    for (int i=1;i<=cnt;i++) vis[St[i]]=1;
    int L,R;
    for (R=1;R<=cnt;R++)
    {
        int sz=Bfs(St[R]);
        ll mx=-1;
        for (int i=2;i<=sz;i++) mx=max(mx,Dist[Queue[i]]);
        if (mx==Sum2[R]) break;
    }

    mem(vis,0);
    for (int i=1;i<=cnt;i++) vis[St[i]]=1;
    for (L=cnt;L>=1;L--)
    {
        int sz=Bfs(St[L]);
        ll mx=-1;
        for (int i=2;i<=sz;i++) mx=max(mx,Dist[Queue[i]]);
        if (mx==Sum1[L]) break;
    }
    L=max(1,L);R=min(R,cnt);

    printf("%lld\n%d\n",Ans,R-L);
    return 0;
}

void Add_Edge(int u,int v,int w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;V[edgecnt]=u;W[edgecnt]=w;
    return;
}

int Bfs(int S)
{
    int h=1,t=0;Queue[1]=S;vis[S]=1;Dist[S]=0;Fa[S]=0;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if (vis[V[i]]==0)
                Dist[Queue[++h]=V[i]]=Dist[u]+W[i],vis[V[i]]=1,Fa[V[i]]=u;
    }
    while (t!=h);
    return t;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3124/Luogu3304][SDOI2013]直径(树的直径)


HNCJ OIer 一枚