传送门
解题思路
若强制在线，可以考虑用树剖+主席树，相当于每次询问两个点之间的路径上在 \(i-C_i\) 时刻之前开始搜集情报的人数。
但是这题可以离线，于是可以把询问按照 \(i-C_i\) 离线一下，就可以用线段树/树状数组来维护了。
注意一定要区分原编号和dfn编号。
时间复杂度：\(O(nlog^2n)\)
当然可以优化到一个log：不用树剖。
直接维护dfs序上差分，每次更新一个点相当于更新以它为根的整个子树，每次查询转化为两次单点查询和查询LCA、fa[LCA]的信息。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<bitset>
#include<stack>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
const int maxn=4e5+5;
int n,m,t[maxn],cnt,p[maxn],siz[maxn],dep[maxn],tp[maxn],cntt,num;
int son[maxn],dfn[maxn],times,d[maxn],fa[maxn],rt;
struct node{
int v,next;
}e[maxn];
struct Node{
int ans1,ans2,c,x,y,id;
}q[maxn];
bool cmp1(Node a,Node b){
return a.c<b.c;
}
bool cmp2(Node a,Node b){
return a.id<b.id;
}
void insert(int u,int v){
cnt++;
e[cnt].v=v;
e[cnt].next=p[u];
p[u]=cnt;
}
void dfs1(int u){
siz[u]=1;
for(int i=p[u];i!=-1;i=e[i].next){
int v=e[i].v;
dep[v]=dep[u]+1;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int top){
dfn[u]=++times;
tp[u]=top;
if(son[u]) dfs2(son[u],top);
for(int i=p[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(v==son[u]) continue;
dfs2(v,v);
}
}
inline int lowbit(int x){
return x&-x;
}
void update(int x){
for(int i=x;i<=n;i+=lowbit(i)) d[i]++;
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res+=d[i];
return res;
}
void get_ans(Node &a){
int x=a.x,y=a.y;
while(tp[x]!=tp[y]){
if(dep[tp[x]]>dep[tp[y]]) swap(x,y);
a.ans2+=query(dfn[y])-query(dfn[tp[y]]-1);
y=fa[tp[y]];
}
if(dep[x]>dep[y]) swap(x,y);
a.ans1=dep[a.x]+dep[a.y]-2*dep[x]+1;
a.ans2+=query(dfn[y])-query(dfn[x]-1);
}
int main(){
memset(p,-1,sizeof(p));
read(n);
for(int i=1;i<=n;i++){
int x;
read(x);
if(x==0) rt=i;
else insert(x,i),fa[i]=x;
}
dfs1(rt);
dfs2(rt,rt);
read(m);
for(int i=1;i<=m;i++){
int ty;
read(ty);
if(ty==1){
int x,y,c;
read(x);read(y);read(c);
q[++num].x=x;
q[num].y=y;
q[num].c=i-c;
q[num].id=i;
}else{
int x;
read(x);
t[i]=x;
}
}
sort(q+1,q+num+1,cmp1);
int now=1;
for(int i=1;i<=m;i++){
while(now<=num&&q[now].c<=i) get_ans(q[now]),now++;
if(t[i]) update(dfn[t[i]]);
}
while(now<=num) get_ans(q[now]),now++;
sort(q+1,q+num+1,cmp2);
for(int i=1;i<=num;i++) print(q[i].ans1),putchar(' '),print(q[i].ans2),puts("");
return 0;
}