Vexoben
Feb 10, 2018
题目链接：http://codeforces.com/problemset/problem/686/D
题意
给定一颗n个节点的树，q次询问，每次询问以节点x为根的子树的重心。
n,q<=300000
题解
又糊了一个和标算不一样的做法。
标算：根据重心的一个性质：把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。对于我们从点1开始往下进行遍历，返回的时候就可以可以看成一颗树与另一颗树相连求重心。
我的算法：考虑以一个点为根的子树，要么这个点为重心，要么重心在这个点最大的子树内。将所有连接节点与其最大子树的边连成一条链，则重心就在链上。于是维护一个倍增数组son，son[x][i]表示以x点为起点，沿着这条链条跳2^i条边到达的点，每次暴力倍增求解即可。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<time.h>
#include<vector>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=3e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m,E,k,siz[N],fa[N];
int nex[N<<1],fir[N],arr[N<<1],son[N][23];
namespace FastIO {
template<typename tp> inline void read(tp &x) {
x=0; register char c=getchar(); register bool f=0;
for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
if(f) x=-x;
}
template<typename tp> inline void write(tp x) {
if (x==0) return (void) (putchar('0'));
if (x<0) putchar('-'),x=-x;
int pr[20]; register int cnt=0;
for (;x;x/=10) pr[++cnt]=x%10;
while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x) {
write(x);
putchar('\n');
}
}
using namespace FastIO;
void Add_Edge(int x,int y) {
nex[++E]=fir[x];
fir[x]=E;
arr[E]=y;
}
void dfs1(int x) {
siz[x]=1;
for (int i=fir[x];i;i=nex[i]) {
if (arr[i]!=fa[x]) {
fa[arr[i]]=x;
dfs1(arr[i]);
siz[x]+=siz[arr[i]];
}
}
for (int i=fir[x];i;i=nex[i])
if (arr[i]!=fa[x])
if (siz[arr[i]]>siz[son[x][0]]) {
son[x][0]=arr[i];
}
for (int i=1;i<=20;i++)
son[x][i]=son[son[x][i-1]][i-1];
}
int check(int x,int y) {
if (!y) return 0;
return 2*siz[y]>=siz[x];
}
int main() {
read(n); read(m);
for (int i=2;i<=n;i++) {
int x; read(x);
Add_Edge(x,i);
Add_Edge(i,x);
}
dfs1(1);
for (int i=1;i<=m;i++) {
int x; read(x);
int y=x;
for (int i=20;i>=0;i--) {
if ((siz[son[y][0]]+siz[son[y][0]]<=siz[x])&&(2*siz[y]>=siz[x])) break;
else if (check(x,son[y][i])) y=son[y][i];
}
writeln(y);
}
return 0;
}