[bzoj4448]-[SCOI2015]情报传递

题目（BZOJ）
题目（洛谷）
 
这题就是让你进行树上单点更新，区间查询。
先来看操作2：你会发现操作2对答案的贡献与它是第几个查询有关（废话），
所以我们可以离线处理每个操作2，将该加的值加进去，然后操作1就是裸的树剖了。
这个需要主席树来解决。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=200050;
int n,Q,tim[N];
struct edge{
	int vk,nxt;
}e[N<<1];
struct querys{
	int k,x,y,c,t,id;
}q[N];
int tt,head[N];
inline void ad(int u,int v){e[++tt].vk=v;e[tt].nxt=head[u];head[u]=tt;}
int dep[N],f[N],son[N],id[N],pre[N],siz[N],top[N],idx;
int root[N*50],tsz,ls[N*50],rs[N*50],sz[N*50];
void dfs1(int u,int fa){
	f[u]=fa;siz[u]=1;dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].vk;
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int fa){
	top[u]=fa;
	id[u]=++idx;pre[id[u]]=u;
	if(!son[u])return;
	dfs2(son[u],fa);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].vk;
		if(v==f[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
inline int lca(int x,int y){for(;top[x]!=top[y];dep[top[x]]>dep[top[y]]?x=f[top[x]]:y=f[top[y]]);return dep[x]<dep[y]?x:y;}
void insert(int l,int r,int x,int &y,int v){
	y=++tsz;sz[y]=sz[x]+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(v<=mid)rs[y]=rs[x],insert(l,mid,ls[x],ls[y],v);
	else ls[y]=ls[x],insert(mid+1,r,rs[x],rs[y],v);
}
inline int query(int x,int y,int c){
	int L=root[x-1],R=root[y],l=1,r=Q,ret=0;
	while(l!=r){
		int mid=(l+r)>>1;
		if(c<=mid)L=ls[L],R=ls[R],r=mid;
		else ret+=sz[ls[R]]-sz[ls[L]],L=rs[L],R=rs[R],l=mid+1;
	}
	ret+=(c>=l?sz[R]-sz[L]:0);
	return ret;
}
inline void solve(int x,int y,int c){
	int ans1=dep[x]+dep[y]-2*dep[lca(x,y)]+1,ans2=0;
	int f1=top[x],f2=top[y];
	while(f1!=f2){
		if(dep[f1]<dep[f2])swap(x,y),swap(f1,f2);
		ans2+=query(id[f1],id[x],c);
		x=f[f1];f1=top[x];
	}
	if(dep[x]<dep[y])swap(x,y);
	ans2+=query(id[y],id[x],c);
	printf(
}
int main(){
	read(n);
	for(int i=1;i<=n;++i){
		int Father;read(Father);
		if(Father!=0)ad(Father,i),ad(i,Father);
	}
	dfs1(1,0);dfs2(1,1);
	read(Q);
	for(int i=1;i<=n;++i)tim[i]=Q;
	for(int i=1;i<=Q;++i){
		int opt;read(opt);
		if(opt==1){
			int x,y,c;read(x),read(y),read(c);
			q[i]=(querys){opt,x,y,i-c-1,0,i};
		}
		else{
			int t;read(t);
			tim[t]=i;
		}
	}
	for(int i=1;i<=n;++i)insert(1,Q,root[i-1],root[i],tim[pre[i]]);
	for(int i=1;i<=Q;++i)if(q[i].k==1)solve(q[i].x,q[i].y,q[i].c);
	return 0;
}