宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

[SCOI2015]情报传递

BZOJ
luogu
考虑什么样的点会对某个询问贡献答案,
设每个点的开始搜集情报时间为t_i),那么每次询问就是要求链上有多少点i满足$$now-t_i>c$$
移项就有$$t_i<now-c$$
相当于求链上满足条件的点数,但是带修改依然不太好做
我们发现对于一个询问后面的修改操作的t_i)一定大于now,所以后面修改的点一定不影响前面询问的答案,
想到什么?
可以离线询问,将所有修改操作处理完,最后直接主席树查就行了,复杂度Onlogn))

#include<bits/stdc++.h>
using namespace std;
const int _=2e5+5;
int re){
	int x=0,w=1;char ch=getchar);
	whilech<'0'||ch>'9'){ifch=='-')w=-1;ch=getchar);}
	whilech>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar);
	return x*w;
}
bool vis[_];
vector<int>p[_];
int n,o,q,cnt,tot;
int s[_*20],ls[_*20],rs[_*20];
int h[_],rt[_],t[_],a[_],b[_],lim[_],fa[_],f[_],lca[_],dep[_];
struct edge{int to,next;}e[_<<1];
void linkint u,int v){
	e[++cnt]=edge){v,h[u]};h[u]=cnt;
	e[++cnt]=edge){u,h[v]};h[v]=cnt;
}
int findint x){return x==f[x]?x:f[x]=findf[x]);}
void updint&x,int l,int r,int k){
	s[++tot]=s[x]+1;ls[tot]=ls[x];rs[tot]=rs[x];
	x=tot;ifl==r)return;int mid=l+r>>1;
	k<=mid?updls[x],l,mid,k):updrs[x],mid+1,r,k);
}
int queryint A,int B,int C,int D,int l,int r,int k){
	ifr<=k)return s[A]+s[B]-s[C]-s[D];
	int mid=l+r>>1,res=queryls[A],ls[B],ls[C],ls[D],l,mid,k);
	ifk>mid)res+=queryrs[A],rs[B],rs[C],rs[D],mid+1,r,k);return res;
}
void dfsint u){
	rt[u]=rt[fa[u]];
	ift[u])updrt[u],1,q,t[u]);
	forint i=h[u];i;i=e[i].next){
		int v=e[i].to;ifv==fa[u])continue;
		dep[v]=dep[u]+1;dfsv);f[v]=u;
	}
	vis[u]=1;
	forint i=0,j=p[u].size);i<j;i++){
		int k=p[u][i],v=a[k]==u?b[k]:a[k];
		ifvis[v])lca[k]=findv);
	}
}
int main){
	n=re);
	forint i=1;i<=n;i++){
		fa[i]=re);if!fa[i])o=i;
		linki,fa[i]);f[i]=i;
	}
	q=re);int op,x;
	forint i=1;i<=q;i++){
		op=re);x=re);
		ifop==2&&!t[x])t[x]=i;
		ifop==1){
			a[i]=x,b[i]=re),lim[i]=i-re)-1;
			p[x].push_backi);p[b[i]].push_backi);
		}
	}
	dep[1]=1;dfso);
	forint i=1;i<=q;i++)
		ifa[i])printf"%d %d
",dep[a[i]]+dep[b[i]]-dep[lca[i]]-dep[fa[lca[i]]],lim[i]>=1?queryrt[a[i]],rt[b[i]],rt[lca[i]],rt[fa[lca[i]]],1,q,lim[i]):0);
	return 0;
}