题解 P7238 【迷失森林】

RedLycoris · 2021-01-02 18:21:29 · 题解

这里是验题人的思路（不同于官方题解）

将所有的树都缩成一个点。 对于第 i 棵树，如果与第 j棵树有边，那么 dist_{i,j} 为第 i 棵树的 i 号点到第j 棵树的 j 号点的距离。

叶子节点要特判。

尤其要特判当1号节点为叶子（只有一条出边）时的情况。

最后对新图求直径即可。

Code:

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int maxn=100004;
char buffer[maxn],*S,*T;
inline char Get_Char(){
    if(S==T){
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}

inline int read(){
    char c;
    ri re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)return -re;
    return re;
}

inline void read(int&x){
    char c;
    ri re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
const int mxn=1e6+6;
vector<int>f[mxn];
vector<pair<int,int> >g[mxn];
int n,root;
int u[mxn],v[mxn];
int pa[mxn];
int dep[mxn];
int max_deep;
int mxdp[mxn];
inline void dfs1(int x,int par=-1,int deep=1){
    mxdp[x]=1;
    dep[x]=deep;pa[x]=par;
    max_deep=max(max_deep,deep);
    for(ri i=0;i<f[x].size();++i){
        ri y=f[x][i];
        if(y!=par)dfs1(y,x,deep+1),mxdp[x]=max(mxdp[x],mxdp[y]+1);
    }
}
ll dist[mxn];
inline void dfs2(int x,int par=-1,ll dst=0){
    dist[x]=dst;
    for(ri i=0;i<g[x].size();++i){
        ri y=g[x][i].first;ll w=g[x][i].second;
        if(y!=par)dfs2(y,x,dst+w);
    }
}
inline void solve(){
    read(n); 
    for(ri i=1;i<n;++i){
        read(u[i]),read(v[i]);
        f[u[i]].push_back(v[i]);
        f[v[i]].push_back(u[i]);
    }
    root=1;
    dfs1(root);//对原树进行处理
    for(ri i=1;i<n;++i){   //将树缩成点
        if((u[i]==1 or v[i]==1) and f[1].size()==1){
            int t;
            if(u[i]==1)t=v[i];
            else t=u[i];
            g[u[i]].push_back(mp(v[i],max_deep+dep[t]-1));
            g[v[i]].push_back(mp(u[i],max_deep+dep[t]-1));
        }else if(f[u[i]].size()==1 or f[v[i]].size()==1){
            g[u[i]].push_back(mp(v[i],max_deep));
            g[v[i]].push_back(mp(u[i],max_deep));
        }else if(u[i]==pa[v[i]]){
            g[u[i]].push_back(mp(v[i],dep[v[i]]));
            g[v[i]].push_back(mp(u[i],dep[v[i]]));              
        }else{
            g[u[i]].push_back(mp(v[i],dep[u[i]]));
            g[v[i]].push_back(mp(u[i],dep[u[i]]));
        }
    }
    memset(dist,63,sizeof(dist)); //求直径
    dfs2(root);
    ri place;
    place=1;
    for(ri i=1;i<=n;++i)if(dist[i]>dist[place])place=i;
    memset(dist,63,sizeof(dist));
    dfs2(place);
    ll Max=0;
    for(ri i=1;i<=n;++i)Max=max(Max,dist[i]);
    printf("%lld\n",Max+1);
}
int main(){
    ios_base::sync_with_stdio(false);
    int T=1;//cin>>T;
    for(;T--;)solve();
    return 0;
}