题目
题目描述
奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名 (可能没有) 下线，除 $1$ 名大头目外其余 $n-1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严，每名情报员只能与自己的上、下线联系，同时，情报网络中任意两名情报员一定能够通过情报网络传递情报。
奈特公司每天会派发以下两种任务中的一个任务：
- 搜集情报：指派 $T$ 号情报员搜集情报；
- 传递情报：将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员。
情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为 $0$；一旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加 $1$ 点危险值 (开始搜集情报的当天危险值仍为 $0$，第 $2$ 天危险值为 $1$，第 $3$ 天危险值为 $2$，以此类推)。传递情报并不会使情报员的危险值增加。
为了保证传递情报的过程相对安全，每条情报都有一个风险控制值 $C$。奈特公司认为，参与传递这条情报的所有情报员中，危险值大于 $C$ 的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。
输入输出格式
输入格式：
第一行包含一个正整数 $n$ ，表示情报员个数。 笫二行包含 $n$ 个非负整数，其中第 $i$ 个整数 $P_i$ 表示 $i$ 号情报员上线的编号。特别地，若 $P_i=0$，表示 $i$号情报员是大头目。 第三行包含一个正整数 $q$，表示奈特公司将派发 $q$ 个任务 (每天一个)。
随后 $q$ 行，依次描述 $q$ 个任务。每行首先有一个正整数 $k$。
- 若 $k=1$，表示任务是传递情报，随后有三个正整数 $X_i$、$Y_i$、$C_i$，依次表示传递情报的起点、终点和风险控制值。
- 若 $k=2$，表示任务是搜集情报，随后有 $1$ 个正整数 $T_i$，表示搜集情报的情报员编号。
输出格式：
对于每个传递情报任务输出一行，包含两个整数，分别是参与传递情报的情报员个数和对该条情报构成威胁的情报员个数。
输入输出样例
输入样例#1：
7
0 1 1 2 2 3 3
6
1 4 7 0
2 1
2 4
2 7
1 4 7 1
1 4 7 3
输出样例#1：
5 0
5 2
5 1
说明
样例解释：
对于 $3$ 个传递情报任务，都是经过 $5$ 名情报员，分别是 $4$ 号、$2$ 号、$1$ 号、$3$号和 $7$ 号。
- 第 $1$ 个任务，所有情报员 (危险值为 $0$) 都不对情报构成威胁；
- 第 $2$ 个任务，有 $2$ 名情报员对情报构成威胁，分别是 $1$ 号情报员 (危险值为 $3$) 和 $4$ 号情报员 (危险值为 $2$)，$7$ 号情报员 (危险值为 $1$) 并不构成威胁；
- 第 $3$ 个任务，只有 $1$ 名情报员对情报构成威胁。
数据范围：
$n\leqslant 2\times 10^5,Q\leqslant 2\times 10^5,0<P_i,C_i\leqslant N,1\leqslant T_i,X_i,Y_i\leqslant n$
题解
把每个点的值定为收集情报的起始时间，这样第$i$个询问主席树查询链上值在$[1,i-C_i-1]$的值有多少个即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct p{
int x,l,r;
}s[MAX<<5];
struct q{
int x,y,c,id;
}qu[MAX];
struct o{
int x,y;
}c[MAX];
int n,m,cnt,tot,num;
int fa[MAX],rt[MAX],T[MAX],siz[MAX],h[MAX],son[MAX],top[MAX],d[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void change(int l,int r,int &k,int pre,int x)
{
s[k=++tot]=s[pre],++s[k].x;
if(l==r) return;
if(x<=mid) change(l,mid,tl,s[pre].l,x);
else change(mid+1,r,tr,s[pre].r,x);
}
int ask(int l,int r,int Lk,int Rk,int LCA,int FLCA,int L,int R)
{
if(r<L||R<l) return 0;
if(l>=L&&r<=R) return s[Lk].x+s[Rk].x-s[LCA].x-s[FLCA].x;
return ask(l,mid,s[Lk].l,s[Rk].l,s[LCA].l,s[FLCA].l,L,R)+ask(mid+1,r,s[Lk].r,s[Rk].r,s[LCA].r,s[FLCA].r,L,R);
}
void dfs(int x=1)
{
if(T[x]) change(1,n,rt[x],rt[fa[x]],T[x]);
else rt[x]=rt[fa[x]];
d[x]=d[fa[x]]+(siz[x]=1);
for(int i=h[x];i;i=c[i].x)
{
dfs(c[i].y),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
}
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp;
if(!son[x]) return;
dfs1(son[x],tp);
for(int i=h[x];i;i=c[i].x)
if(c[i].y^son[x]) dfs1(c[i].y,c[i].y);
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
return d[x]>d[y]?y:x;
}
void add(int x,int y) {c[++num]=(o){h[x],y},h[x]=num;}
int main()
{
n=read();
for(int i=1;i<=n;++i)
{
fa[i]=read();
if(fa[i]) add(fa[i],i);
}
m=read();
for(int i=1,k,x,y;i<=m;++i)
{
k=read();
if(k==1) x=read(),y=read(),qu[++cnt]=(q){x,y,read(),i};
else if(k==2) T[read()]=i;
}
dfs(),dfs1();
for(int i=1,lca;i<=cnt;++i)
lca=LCA(qu[i].x,qu[i].y),printf("%d %d\n",d[qu[i].x]+d[qu[i].y]-(d[lca]<<1)+1,ask(1,n,rt[qu[i].x],rt[qu[i].y],rt[lca],rt[fa[lca]],1,qu[i].id-qu[i].c-1));
return 0;
}
