求助,62分
查看原帖
求助,62分
455490
Sharpsmile楼主2021/10/16 16:07

蒟蒻死了,第29个点还是啥。。。咋错的不是很懂

求各位大佬们帮忙看看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;
struct node{int  dep,maxdep;}a[100020];
int n,m,r;
struct edge{int v,nt;}e[200400];
int f[100200],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[100200];
bool vis[100020];
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;
            dfs(e[i].v);
a[id].maxdep=max(a[id].maxdep,a[e[i].v].maxdep);
        }
}
inline void reit(){
    node x={0,0};
    for(int i=1;i<=n+1;i++){
        a[i]=x;
    }
    memset(vis,0,sizeof(vis));
}
void dfst(int dep,int id){
    vis[id]=1;
    if(dep>maxdep){
        loca=id;
        maxdep=dep;
    }
    for(int i=f[id];i;i=e[i].nt)
        if(!vis[e[i].v]){
            dfst(dep+1,e[i].v);
        }
    
}
bool vx[100020],vy[100020];
int fd(int x,int y){
    queue<int >qx,qy;
    memset(vx,0,sizeof(vx));
    memset(vy,0,sizeof(vy));
    vx[x]=vy[y]=1;
    bool w=1;
    qx.push(x);
    qy.push(y);
    while(!qx.empty()&&!qy.empty()){
        if(w){int id=qx.front();
            //cout<<id<<" ";
            qx.pop();
            if(vy[id])return id;
            for(int i=f[id];i;i=e[i].nt){
                    if(!vx[e[i].v]){
                       
                        vx[e[i].v]=1;
                        qx.push(e[i].v);
                    }
            }
                }
        else{ int id=qy.front();//cout<<id<<" ";
            qy.pop();
            if(vx[id]) return id;
            for(int i=f[id];i;i=e[i].nt){
                    if(!vy[e[i].v]){
                        vy[e[i].v]=1;
                        qy.push(e[i].v);
                    }
            }
        }
        w=!w;
    }
    return x;
    
}
int k;
bool cmp(int x,int y){
    return x>y;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    maxdep=-1;
    reit();
    dfst(1,1);

    root=loca;
    maxdep=-1;
    reit();
    dfst(1,loca);
    
    //cout<<root<<" "<<loca<<endl;
    root=fd(root,loca);
    reit();
    dfs(root);
    //cout<<root<<endl;
    for(int i=1;i<=n;i++){
        ans[i]=a[i].maxdep-a[i].dep;
    }
    sort(ans+1,ans+n+1,cmp);
    cout<<ans[k+1]+1;
    return 0;
}

2021/10/16 16:07
加载中...