2019.01.14 codeforces685B. Kay and Snowflake（树形dp）

传送门

题意简述：给出一棵树，求每个子树的重心。

首先通过画图可以观察出一个性质，我们从叶子结点向根节点递推重心的话重心的位置是不会下降的。

然后由于一个点的重心要么是自己，要么在重儿子子树内，因此如果重心不是自己，我们从重儿子子树的重心向自己爬统计答案就行了，由于重心不会下降因此时间复杂度O(n)O(n)O(n)

代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=3e5+5;
int n,q,siz[N],fa[N],dep[N],hson[N],ans[N];
vector<int>e[N];
void dfs1(int p){
	siz[p]=1;
	for(ri i=0,v;i<e[p].size();++i){
		v=e[p][i];
		fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
		if(siz[v]>siz[hson[p]])hson[p]=v;
	}
}
void dfs2(int p){
	if(!hson[p]){ans[p]=p;return;}
	for(ri i=0;i<e[p].size();++i)dfs2(e[p][i]);
	if(siz[hson[p]]*2<=siz[p])ans[p]=p;
	else for(ri v=ans[hson[p]];v!=p;v=fa[v])if(max(siz[hson[v]],siz[p]-siz[v])*2<=siz[p]){ans[p]=v;break;}
}
int main(){
	n=read(),q=read();
	for(ri i=2;i<=n;++i)e[read()].push_back(i);
	dfs1(1),dfs2(1);
	while(q--)cout<<ans[read()]<<'\n';
	return 0;
}

巴特西

2019.01.14 codeforces685B. Kay and Snowflake（树形dp）

最新文章

热门文章