首先进行题意转换，假设当前操作的时间是第 $i$ 天，那么搜集情报就是将指定的节点 $t$ 打上标记 $i$，传递情报就是查询 $u$ 到 $v$ 之间的点的个数以及打了标记的且标记小于 $i - c$ 的点的个数。

这篇题解就是介绍一下 $O(n \log^2 n)$ 的在线树剖套主席树做法。严谨一点，其实是 $O(n + q \log^2 n)$。

不知道为啥题解区里都说是 $O(n \log^3 n)$ 的，感觉也不难想。

第 $i$ 天对于搜集情报，如果 $t$ 是第一次搜集情报，则在版本 $i - 1$ 的基础上给节点 $t$ 标记为 $1$ 作为版本 $i$，否则直接把版本 $i - 1$ 复制给版本 $i$；对于传递情报就是查询 $u$ 到 $v$ 上节点的个数和版本 $\max(i - c - 1,0)$ 中 $u$ 到 $v$ 的路径上标记了的点的个数，把版本 $i - 1$ 复制给版本 $i$。用树剖套主席树能实现以上所说的。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,root,sz[N],fa[N],d[N],son[N],rk[N],tp[N],vis[N],tot=0,rt[N],sum[N<<5],ls[N<<5],rs[N<<5],head[N],cnt=0,dfn=0;
struct node {int to,nxt;}e[N];
void add(int u,int v) {e[++cnt]=(node){v,head[u]};head[u]=cnt;}
void dfs1(int u,int pre,int dep) {
	int mx=0;
	sz[u]=1,fa[u]=pre,d[u]=dep;
	for(int i=head[u]; ~i; i=e[i].nxt) {
		int v=e[i].to;
		if(v==pre) continue;
		dfs1(v,u,dep+1);
		sz[u]+=sz[v];
		if(sz[v]>mx) mx=sz[v],son[u]=v;
	}
}
void dfs2(int u,int top) {
	rk[u]=++dfn,tp[u]=top;
	if(!son[u]) return;
	dfs2(son[u],top);
	for(int i=head[u]; ~i; i=e[i].nxt) {
		int v=e[i].to;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
int build(int l,int r) {
	int x=++tot;
	if(l==r) return x;
	int mid=l+r>>1;
	ls[x]=build(l,mid);
	rs[x]=build(mid+1,r);
	return x;
}
int add(int lst,int l,int r,int a) {
	int x=++tot;
	sum[x]=sum[lst]+1,ls[x]=ls[lst],rs[x]=rs[lst];
	if(l==r) return x;
	int mid=l+r>>1;
	if(a<=mid) ls[x]=add(ls[lst],l,mid,a);
	else rs[x]=add(rs[lst],mid+1,r,a);
	return x;
}
int query(int l,int r,int x,int y,int id) {
	if(l>=x&&r<=y) return sum[id];
	if(r<x||l>y) return 0;
	int mid=l+r>>1;
	return query(l,mid,x,y,ls[id])+query(mid+1,r,x,y,rs[id]);
}
pair<int,int> ask(int x,int y,int id) {
	int ans=0;
	while(tp[x]!=tp[y]) {
		if(d[tp[x]]<d[tp[y]]) swap(x,y);
		ans+=query(1,n,rk[tp[x]],rk[x],rt[id]);
		x=fa[tp[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	return make_pair(x,ans+query(1,n,rk[x],rk[y],rt[id]));
}
int main() {
	cin>>n;
	memset(head,-1,sizeof(head));
	for(int i=1; i<=n; i++) {
		int p;
		cin>>p;
		if(!p) root=i;
		else add(p,i);
	}
	dfs1(root,0,1);
	dfs2(root,root);
	rt[0]=build(1,n);
	cin>>q;
	for(int i=1; i<=q; i++) {
		int op;
		cin>>op;
		if(op==1) {
			int x,y,c;
			cin>>x>>y>>c;
			pair<int,int> p=ask(x,y,max(i-c-1,0));
			cout<<d[x]+d[y]-2*d[p.first]+1<<" "<<p.second<<endl;
			rt[i]=rt[i-1];
		} else {
			int t;
			cin>>t;
			if(!vis[t]) rt[i]=add(rt[i-1],1,n,rk[t]),vis[t]=true;
			else rt[i]=rt[i-1];
		}
	}
}

马蜂丑轻喷。