不难发现,对于一个传递$i$,只有$i-C_i-1$之前的搜集才会对答案产生贡献。

那可以衍生两种算法。

较简单但复杂度较高的离线算法($O(n~log^2n)$):

对于传递$i$,以$i-C_i-1$进行排序,就可以线性推了,对于询问可用树链剖分进行处理。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=2e5+5,mod=20170408;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct Query
{
    int x,y,c,id;
    Query(int x=0,int y=0,int c=0,int id=0):x(x),y(y),c(c),id(id){}
    bool operator <(const Query a)const{return c<a.c;} 
}Q[N];
struct node
{
    int x,t;
    node(int x=0,int t=0):x(x),t(t){}
    bool operator <(const node a)const{return t<a.t;}
}P[N];
int fa[N],siz[N],son[N],dep[N],yss[N],top[N],cnt,dfn[N],c[N],n,ans[N],s[N];
inline void add(int x){for(;x<=n;x+=x&-x)++c[x];}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs1(int x)
{
    siz[x]=1;son[x]=0;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if((y=a[k].y)==fa[x])continue;
        fa[y]=x;dep[y]=dep[x]+1;
        dfs1(y);
        siz[x]+=siz[y];if(siz[son[x]]<siz[y])son[x]=y;
    }
}
void dfs2(int x,int tp)
{
    dfn[x]=++cnt;yss[cnt]=x;top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=fa[x]&&y!=son[x])dfs2(y,y);
}
void solve(int x,int y,int id)
{
    int tx=top[x],ty=top[y];ans[id]=0,s[id]=0;
    while(tx!=ty)
    {
        if(dep[tx]>dep[ty])
            s[id]+=dep[x]-dep[tx]+1,ans[id]+=ask(dfn[x])-ask(dfn[tx]-1),x=fa[tx],tx=top[x];
        else 
            s[id]+=dep[y]-dep[ty]+1,ans[id]+=ask(dfn[y])-ask(dfn[ty]-1),y=fa[ty],ty=top[y];
    }
    if(dep[x]<dep[y])swap(x,y);
    s[id]+=dep[x]-dep[y]+1,ans[id]+=ask(dfn[x])-ask(dfn[y]-1);
}
int main()
{
    qr(n);int rt=0;
    for(int i=1,x;i<=n;i++)
    {
        qr(x);
        if(!x)rt=i;
        else ins(x,i),ins(i,x); 
    }
    dfs1(rt);
    dfs2(rt,rt);
    int m;qr(m);
    int l1=0,l2=0;
    for(int i=1;i<=m;i++)
    {
        int op,x,y,w;qr(op),qr(x);
        if(op==1)qr(y),qr(w),++l1,Q[l1]=Query(x,y,i-w-1,l1);
        else P[++l2]=node(x,i);
    }
    sort(Q+1,Q+l1+1);sort(P+1,P+l2+1);
    for(int i=1,j=0;i<=l1;i++)
    {
        while(j+1<=l2&&P[j+1].t<=Q[i].c)++j,add(dfn[P[j].x]);
        solve(Q[i].x,Q[i].y,Q[i].id);
    }
    for(int i=1;i<=l1;i++)
        qw(s[i]),putchar(' '),qw(ans[i]),puts("");
    return 0;
}

较复杂但复杂度较低的在线算法($O(n~log~n)$):

根据$i-C_i-1$这个条件,不难联想到可以存版本,就可以利用可持久化进行操作。

利用类似树上的差分,可以把询问拆成$s_x+s_y-s_{lca(x,y)}-s_{fa_{lca(x,y)}}$,其中$s_i$表示$i$点到根节点有多少个可以产生贡献的情报员。

修改操作可以使用标记永久化。

悄悄bb一句,树剖在跑得更快($n,q\le 2e5$)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=2e5+5,mod=20170408;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int fa[N],siz[N],son[N],dep[N],yss[N],top[N],cnt,dfn[N],c[N],n;
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs1(int x)
{
    siz[x]=1;son[x]=0;
    for(int k=last[x],y;k;k=a[k].next)
    {
        if((y=a[k].y)==fa[x])continue;
        fa[y]=x;dep[y]=dep[x]+1;
        dfs1(y);
        siz[x]+=siz[y];if(siz[son[x]]<siz[y])son[x]=y;
    }
}
void dfs2(int x,int tp)
{
    dfn[x]=++cnt;yss[cnt]=x;top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=fa[x]&&y!=son[x])dfs2(y,y);
}
int lca(int x,int y)
{
    int tx=top[x],ty=top[y];
    while(tx!=ty)
    {
        if(dep[tx]>dep[ty])x=fa[tx],tx=top[x];
        else y=fa[ty],ty=top[y];
    }
    if(dep[x]<dep[y])swap(x,y);
    return y;
}
struct HGT{int l,r,s;}t[N<<5];int root[N],tmp,id[N];//标记永久化可持久化线段树 
bool vis[N];
void update(int l,int r,int &x,int y,int L,int R)
{
    t[x=++tmp]=t[y];
    if(L<=l&&R>=r){t[x].s++;return ;}
    int mid=l+r>>1;
    if(L<=mid)update(l,mid,t[x].l,t[y].l,L,R);
    if(R>mid)update(mid+1,r,t[x].r,t[y].r,L,R);
}
int query(int l,int r,int x,int pos)
{
    if(l==r)return t[x].s;
    int mid=l+r>>1,val=0;
    if(pos<=mid)val+=query(l,mid,t[x].l,pos);
    else val+=query(mid+1,r,t[x].r,pos);
    return val+t[x].s;
}
int calc(int t,int x)
{
    if(!id[t]||!dfn[x])return 0;
    return query(1,n,root[id[t]],dfn[x]);
}
int main()
{
    qr(n);int rt=0;
    for(int i=1,x;i<=n;i++)
    {
        qr(x);
        if(!x)rt=i;
        else ins(x,i),ins(i,x); 
    }
    dep[1]=1;dfs1(rt);
    dfs2(rt,rt);
    int m;qr(m);
    for(int i=1;i<=m;i++)
    {
        int op,x,y,c;qr(op);
        if(op==1)
        {
            qr(x),qr(y),qr(c);
            id[i]=id[i-1];int t=max(i-c-1,0);
            int f=lca(x,y),ans=calc(t,x)+calc(t,y)-calc(t,f)-calc(t,fa[f]);
            qw(dep[x]+dep[y]-dep[f]-dep[fa[f]]);putchar(' ');qw(ans);puts("");
        }
        else
        {
            qr(x);
            if(vis[x])continue;vis[x]=1;//只有第一次才算。 
            id[i]=id[i-1]+1;
            update(1,n,root[id[i]],root[id[i-1]],dfn[x],dfn[x]+siz[x]-1);
        }
    }
    return 0;
}