萌新求救,36分
查看原帖
萌新求救,36分
455490
Sharpsmile楼主2021/11/9 08:07

诶。。。。。。

就36分

sub1 WA2个

sub 2 3 4 AC

sub5 全WA

sub6 WA3个

求大佬们来帮一下QAQ

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#define Inf 1e8;
using namespace std;
#define int long long
struct node{int  dep,maxdep,ansdep;}a[1000020];
int n,m,r;
struct edge{int v,nt;}e[2000400];
int f[1000200],cnt;
int loca,root,maxdep;
inline void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].nt=f[u];
    f[u]=cnt;
}
int ans[1000200];
bool vis[1000020];
int fa[1000300];
void dfs(int id){
    vis[id]=1;
    a[id].maxdep=a[id].dep;
    for(int i=f[id];i;i=e[i].nt)
        if(!vis[e[i].v]){
            a[e[i].v].dep=a[id].dep+1;
            fa[e[i].v]=id;
            dfs(e[i].v);
a[id].maxdep=max(a[id].maxdep,a[e[i].v].maxdep);
        }
}
int dp[1002000];
inline void dfsans(int id){
    vis[id]=1;
    a[id].ansdep=-1;
    for(int i=f[id];i;i=e[i].nt){
      
            if(!vis[e[i].v]){
                dfsans(e[i].v);
                a[id].ansdep=max(a[id].ansdep,a[e[i].v].ansdep+a[id].dep+1);
            }
    }
    if(a[id].ansdep==-1){
        a[id].ansdep=a[1].maxdep;
    }
   
}
int k;
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1);
    memset(vis,0,sizeof(vis));
    dfsans(1);
    int lastans1=0,lastans2=0;
    for(int i=f[1];i;i=e[i].nt){
        int v=e[i].v;
        if(a[v].ansdep+a[1].dep+1>lastans1){
            lastans2=lastans1;
            lastans1=a[v].ansdep+1+a[1].dep;
        }
        else if(a[v].ansdep+1>lastans2){
            lastans2=a[v].ansdep+1+a[1].dep;
        }
    }
    cout<<max(lastans2+lastans1+1,lastans1+a[1].maxdep+1)<<endl;
    return 0;
}

2021/11/9 08:07
加载中...