首页 > 代码库 > CodeForces 685B Kay and Snowflake
CodeForces 685B Kay and Snowflake
树的重心，树形$dp$。
记录以$x$为$root$的子树的节点个数为$sz[x]$，重儿子为$son[x]$，重心为$ans[x]$。
首先要知道一个结论：以$x$为$root$的子树的重心$ans[x]$，一定在$ans[son[x]]$到$x$的路径上，即以$x$的重儿子为根的子树的重心到$x$的路径上。
因此，只要从节点$ans[son[x]]$依次往$father$枚举就可以了.
如果枚举到节点$g$，发现$g$节点满足$sz\left[ {son\left[ g \right]} \right] ≤ \frac{{sz\left[ x \right]}}{2}\& \& sz\left[ x \right] - sz\left[ g \right] ≤ \frac{{sz\left[ x \right]}}{2}$，那么$ans[x]=g$。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}const int maxn=300010;int n,q,p[maxn],h[maxn],sz[maxn],son[maxn],ans[maxn],cnt;struct Edge {int u,v,nx;}e[maxn];void add(int u,int v){ e[cnt].u=u; e[cnt].v=v; e[cnt].nx=h[u]; h[u]=cnt++;}void dfs(int x){ sz[x]=1; son[x]=0; for(int i=h[x];i!=-1;i=e[i].nx) { dfs(e[i].v); sz[x]=sz[x]+sz[e[i].v]; if(sz[e[i].v]>sz[son[x]]) son[x]=e[i].v; } if(sz[x]==1) { ans[x]=x; return; } int g=ans[son[x]]; while(1) { bool fail=0; if(sz[son[g]]>sz[x]/2) fail=1; if(sz[x]-sz[g]>sz[x]/2) fail=1; if(fail==0) { ans[x]=g; break; } g=p[g]; }}int main(){ //File(); memset(h,-1,sizeof h); cnt=0; scanf("%d%d",&n,&q); for(int i=2;i<=n;i++) { scanf("%d",&p[i]); add(p[i],i); } dfs(1); for(int i=1;i<=q;i++) { int x; scanf("%d",&x); printf("%d\n",ans[x]); } return 0;}
CodeForces 685B Kay and Snowflake
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。