直径+欲張り——cf 1294 F

/*
       ，                
  ：     +         
      ，         dfs      
*/
#include
using namespace std;
#define N 400005

vector<int>G[N];
int n,s,t,d[N],vis[N],id,Max;

void getdeep(int u,int pre){
    for(auto v:G[u]){
        if(v==pre)continue;
        d[v]=d[u]+1;
        getdeep(v,u);
    }
}

vector<int>path;
int getpath(int u,int pre){
    int flag=0;
    if(u==t){path.push_back(u);return 1;}
    for(auto v:G[u]){
        if(v==pre)continue;
        if(getpath(v,u))
            flag=1;
    }
    
    if(flag)path.push_back(u);
    return flag;
}

void dfs(int u,int pre){
    for(auto v:G[u]){
        if(vis[v] || v==pre)continue;
        d[v]=d[u]+1;
        dfs(v,u);
    }
}

int main(){
    cin>>n;
    for(int i=1;i){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }    
    s=1;
    getdeep(s,s);
    for(int i=1;i<=n;i++)
        if(d[i]>d[s])s=i;
    
    memset(d,0,sizeof d);
    getdeep(s,s);
    for(int i=1;i<=n;i++)
        if(d[i]>d[t])t=i;
    int ans=d[t];
        
    getpath(s,s);
//    for(auto x:path)cout<
    memset(d,0,sizeof d);
    for(auto x:path)vis[x]=1;
    for(auto x:path)dfs(x,x);
    Max=-1;
    for(int i=1;i<=n;i++)if(!vis[i]){
        if(Maxi;
    }
    if(Max==-1){
        for(int i=1;i<=n;i++) 
            if(i!=s && i!=t)id=i;
        Max=0;
    }
    ans+=Max;
    
    cout<'
';
    cout<" "<" "<'
';
}