BZOJ4448: [Scoi2015]情报传递

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 200010
using namespace std;
int n,m,c=1;
int head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],top[MAXN];
int val[MAXN],root[MAXN];
struct Tree{
	int next,to;
}a[MAXN];
struct Question{
	int u,v,w;
}que[MAXN];
inline int read(){
	int date=0;char c=0;
	while(c<‘0‘||c>‘9‘)c=getchar();
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date;
}
namespace CT{
	int size=0;
	struct Chairmen_Tree{
		int sum,l,r;
	}a[MAXN*20];
	inline void buildtree(){
		root[0]=a[0].l=a[0].r=a[0].sum=0;
	}
	void insert(int k,int l,int r,int &rt){
		a[++size]=a[rt];rt=size;
		a[rt].sum++;
		if(l==r)return;
		int mid=l+r>>1;
		if(k<=mid)insert(k,l,mid,a[rt].l);
		else insert(k,mid+1,r,a[rt].r);
	}
	int query(int u,int v,int fa,int fafa,int l,int r,int lside,int rside){
		int ans=0;
		if(l<=lside&&rside<=r)return (a[u].sum+a[v].sum-a[fa].sum-a[fafa].sum);
		int mid=lside+rside>>1;
		if(l<=mid)ans+=query(a[u].l,a[v].l,a[fa].l,a[fafa].l,l,r,lside,mid);
		if(mid<r)ans+=query(a[u].r,a[v].r,a[fa].r,a[fafa].r,l,r,mid+1,rside);
		return ans;
	}
}
inline void add(int x,int y){
	a[c].to=y;a[c].next=head[x];head[x]=c++;
}
void dfs1(int rt){
	son[rt]=0;size[rt]=1;
	root[rt]=root[fa[rt]];
	if(val[rt])CT::insert(val[rt],1,m,root[rt]);
	for(int i=head[rt],will;i;i=a[i].next){
		will=a[i].to;
		deep[will]=deep[rt]+1;
		fa[will]=rt;
		dfs1(will);
		size[rt]+=size[will];//就是这里！当初我把两个弄反了。。。然后就。。。
		if(size[son[rt]]<size[will])son[rt]=will;
	}
}
void dfs2(int rt,int f){
	top[rt]=f;
	if(son[rt])dfs2(son[rt],f);
	for(int i=head[rt];i;i=a[i].next){
		int will=a[i].to;
		if(will!=fa[rt]&&will!=son[rt])dfs2(will,will);
	}
}
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y);
	return x;
}
void work(){
	int u,v,w,lca;
	for(int i=1;i<=m;i++)if(que[i].u){
		u=que[i].u;v=que[i].v;w=que[i].w;
		lca=LCA(u,v);
		w=i-w-1;
		printf("%d ",deep[u]+deep[v]-2*deep[lca]+1);
		if(w<1)printf("0\n");
		else printf("%d\n",CT::query(root[u],root[v],root[lca],root[fa[lca]],1,w,1,m));
	}
}
void init(){
	int f,u,root;
	n=read();
	CT::buildtree();
	for(int i=1;i<=n;i++){
		u=read();
		if(u)add(u,i);
		else root=i;
		val[i]=0;
	}
	m=read();
	for(int i=1;i<=m;i++){
		f=read();que[i].u=0;
		if(f==1){
			que[i].u=read();que[i].v=read();que[i].w=read();
		}
		else{
			u=read();
			val[u]=i;
		}
	}
	deep[root]=1;
	dfs1(root);
	dfs2(root,root);
}
int main(){
	init();
	work();
	return 0;
}