/ Randle / 题库 / 树T1 /

题解

1 条题解

  • 0
    @ 2017-11-07 17:20:54
    #include<bits/stdc++.h>
    const int maxn=200001;
    inline const void read(int &a)
    {
        a=0;
        char c=getchar();
        while(c<'0'||c>'9')c=getchar();
        while(c>='0'&&c<='9')
        {
            a=(a<<1)+(a<<3)+c-'0';
            c=getchar();
        }
    }
    inline const void write(int a)
    {
        if(a>=10)write(a/10);
        putchar(a%10+'0');
    }
    inline const int max(int a,int b)
    {
        if(a>b)return a;
        return b;
    }
    inline const int min(int a,int b)
    {
        if(a<b)return a;
        return b;
    }
    int point[maxn],n,d=0,ans=0,to[maxn],next[maxn],start,end,dis[maxn];
    bool been[maxn],on_chain[maxn];
    void dfs1(int p,int tt)
    {
        if(tt==1&&dis[p]>dis[start])start=p;
        if(tt==2&&dis[p]>dis[end])end=p;
        been[p]=true;
        int side=point[p];
        while(side)
        {
            if(!been[to[side]])
            {
                dis[to[side]]=dis[p]+1;
                dfs1(to[side],tt);
            }
            side=next[side];
        }
    }
    bool dfs2(int p)
    {
        if(p==end){on_chain[p]=true;return true;}
        been[p]=true;
        int side=point[p];
        while(side)
        {
            if(!been[to[side]])if(dfs2(to[side]))on_chain[p]=true;
            side=next[side];
        }
        if(on_chain[p])return true;
        else return false;
    }
    void dfs3(int p)
    {
        if(on_chain[p])dis[p]=0;
        if(dis[p]>dis[ans])ans=p;
        been[p]=true;
        int side=point[p];
        while(side)
        {
            if(!been[to[side]])
            {
                dis[to[side]]=dis[p]+1;
                dfs3(to[side]);
            }
            side=next[side];
        }
    }
    inline const void add(int a,int b)
    {
        next[++d]=point[a];
        point[a]=d;
        to[d]=b;
    }
    inline const void init()
    {
        memset(dis,0,sizeof(dis));
        memset(been,false,sizeof(been));
    }
    int main()
    {
        //freopen("测试数据.txt","r",stdin);
        memset(on_chain,false,sizeof(on_chain));
        memset(point,0,sizeof(point));
        read(n);
        for(int i=1;i<=n-1;i++)
        {
            int a,b;
            read(a);read(b);
            add(a,b);add(b,a);
        }
        init();
        dfs1(1,1);
        init();
        dfs1(start,2);
        init();
        dfs2(start);
        init();
        dfs3(start);
        write(dis[ans]);
        return 0;
    }
    
  • 1

信息

难度
9
分类
(无)
标签
(无)
递交数
9
已通过
1
通过率
11%
上传者