树剖求助
查看原帖
树剖求助
157598
Magallan_forever楼主2020/8/14 11:27
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxp=101,maxl=201;
int last_[maxp],to_[maxl],next_[maxl],cnt=0,f[maxp],deep[maxp],size_[maxp],hs[maxp],top[maxp],dfn[maxp],rank_[maxp],clock_=0,deep_[maxp];
void link(int x,int y) { to_[cnt]=y,next_[cnt]=last_[x],last_[x]=cnt++; }
void dfs0(int now){
    hs[now]=0,size_[now]=1;
    for(int i=last_[now];~i;i=next_[i])
        if(!size_[to_[i]]){
            deep[to_[i]]=deep[now]+1,f[to_[i]]=now,dfs0(to_[i]),size_[now]+=size_[to_[i]];
            if(!hs[now]||size_[to_[i]]>size_[hs[now]]) hs[now]=to_[i];
        }
}
void dfs1(int now,int p){
    top[now]=p,dfn[now]=clock_,rank_[clock_++]=now;
    if(hs[now]){
        dfs1(hs[now],p);
        for(int i=last_[now];~i;i=next_[i]) if(to_[i]^hs[now]&&to_[i]^f[now]) dfs1(to_[i],to_[i]);
    }
}
int lca(int x,int y){
    while(top[x]^top[y])
        if(deep[top[x]]>deep[top[y]]) x=f[top[x]];
        else y=f[top[y]];
    return deep[x]>deep[y]?y:x;
}
int main(){
	int n,x,y,lca_,ans1=-1,ans2=-1;
    scanf("%d",&n),memset(last_,-1,sizeof(last_));
    for(int i=1;i<n;++i) scanf("%d%d",&x,&y),link(x,y),link(y,x);
    deep[1]=1,dfs0(1),dfs1(1,1),scanf("%d%d",&x,&y),lca_=lca(x,y);
    for(int i=1;i<=n;++i) ans1=max(ans1,deep[i]),++deep_[deep[i]];
    for(int i=1;i<=n;++i) ans2=max(ans2,deep_[i]);
	if(deep[x]>deep[y]) printf("%d\n%d\n%d",ans1,ans2,(deep[x]-deep[lca_])*2+deep[y]-deep[lca_]);
	else printf("%d\n%d\n%d",ans1,ans2,(deep[y]-deep[lca_])*2+deep[x]-deep[lca_]);
    return 0;
}
2020/8/14 11:27
加载中...