洛谷 P3884 [JLOI2009]二叉树问题
程序员文章站
2022-06-24 08:51:44
[TOC] 题目 "P3884 [JLOI2009]二叉树问题" 思路 深搜统计深度,倍增$\text{LCA}$求边数 $Code$ ......
目录
题目
思路
深搜统计深度,倍增$\text{lca}$求边数
$code$
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #define maxn 100 #define max_(a,b) a>b?a:b; using namespace std; int n,cnt,head[maxn],dep[maxn],fa[maxn][20],lg[maxn]; int sum1,sum2,ans1,ans2[maxn]; struct edge{ int next,to; }edge[maxn<<1]; inline int qpow(int a,int b){ int ans=1,base=a; while(b){ if(b&1) ans*=base; base*=base; b>>=1; } return ans; } inline void addedge(int from,int to){ edge[++cnt].to=to,edge[cnt].next=head[from]; head[from]=cnt; } inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } void dfs(int u,int father){ dep[u]=dep[father]+1; ans2[dep[u]]++; ans1=max_(ans1,dep[u]); fa[u][0]=father; for(int i=head[u];i;i=edge[i].next){ int x=edge[i].to; if(x!=father) dfs(x,u); } } void lca(int x,int y){ if(dep[x]<dep[y]){ while(dep[y]>dep[x]){ sum2+=qpow(2,lg[dep[y]-dep[x]]-1); y=fa[y][lg[dep[y]-dep[x]]-1]; } }else{ while(dep[x]>dep[y]){ sum1+=qpow(2,lg[dep[x]-dep[y]]-1); x=fa[x][lg[dep[x]-dep[y]]-1]; } } if(x==y) return; for(int k=lg[dep[x]]-1;k>=0;--k){ if(fa[x][k]!=fa[y][k]){ sum1+=qpow(2,k),sum2+=qpow(2,k); x=fa[x][k],y=fa[y][k]; } } sum1++,sum2++; } int main(){ n=read(); for(int i=1,u,v;i<n;++i){ u=read(),v=read(); addedge(u,v); addedge(v,u); } dfs(1,0); for(int i=1;(1<<i)<=n;++i){ for(int j=1;j<=n;++j){ fa[j][i]=fa[fa[j][i-1]][i-1]; } } for(int i=1;i<=n;++i){ lg[i]=lg[i-1]+(1<<lg[i-1]==i); } int ans=0; for(int i=1;i<maxn;++i){ if(ans2[i]>ans){ ans=ans2[i]; } } int u,v; u=read(),v=read(); printf("%d\n%d\n",ans1,ans); lca(u,v); printf("%d\n",sum1*2+sum2); return 0; }
上一篇: python画iPhone手机,这种操作有几个人见过?
下一篇: python 数据类型、进制转换