奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 n 名情报员。每名情报员可能有若干名 (可能没有) 下线,除 1 名大头目外其余 n−1 名情报员有且仅有 1 名上线。奈特公司纪律森严,每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。

奈特公司每天会派发以下两种任务中的一个任务:

  1. 搜集情报:指派 T 号情报员搜集情报;
  2. 传递情报:将一条情报从 X 号情报员传递给 Y 号情报员。

情报员最初处于潜伏阶段,他们是相对安全的,我们认为此时所有情报员的危险值为 0;一旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加 1 点危险值 (开始搜集情报的当天危险值仍为 0,第 2 天危险值为 1,第 3 天危险值为 2,以此类推)。传递情报并不会使情报员的危险值增加。

为了保证传递情报的过程相对安全,每条情报都有一个风险控制值 C。奈特公司认为,参与传递这条情报的所有情报员中,危险值大于 C 的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

链接🔗
[SCOI2015]情报传递

题解

将一个情报员开始搜集情报的时刻设为它的权值,对于一个始终没有搜集情报的人,权值设为Q

对于t时刻的询问,显然就是询问路径上比t-c小的值有多少个

询问区间中小于某个数的元素有多少个,显然就是主席树。因为是在树上的,所以我们直接建树上主席树,也就是每个节点继承父节点的信息,然后每次询问找出lca,做两遍询问,再特判一下lca即可

我们先将问题离线,然后情报员的权值设置为开始搜集情报的时刻,然后询问就是查询路径上小于某值的点又多少个

区间查询小于某值的个数可以用主席树做,然后在树上,所以我们可以将主席树上树 ,每棵节点继承父节点的信息,然后查询路径就可以找到两点的LCA,结果就是 点x的树 + 点 y 的树 减去 2 * lca的树, 然后处理一下LCA点的贡献即可

代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define mid ((l+r)>>1)
using namespace std;
const int N = 2e5+10;
struct{ int v,net; }e[N];
struct{ int op,x,y,z;}q[N];
struct{ int ls,rs,v;}t[N*40];
int f[N],eid,tot;
int sz[N],d[N],son[N],top[N],fa[N];
int rt[N],val[N],n,m,root;
void insert(int x,int y)
{
    e[eid].v = y;
    e[eid].net = f[x];
    f[x] = eid++;
}
void dfs1(int x)
{
    sz[x] = 1;
    for(int i=f[x];i+1;i=e[i].net)
    {
        int v = e[i].v;
        d[v] = d[x]+1;
        dfs1(v);sz[x] += sz[v];
        if(sz[v] > sz[son[x]]) son[x] = v; 
    }
}
void dfs2(int x,int tp)
{
    top[x] = tp;
    if(son[x]) dfs2(son[x],tp);
    for(int i=f[x];i+1;i=e[i].net)
    {
        int v  = e[i].v;
        if(v != fa[x]&&v != son[x]) dfs2(v,v); // 不是父亲并且不是重儿子
    }
}
int getlca(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]? x:y;
}
void insert(int &rt,int p,int l,int r,int x)
{
    t[rt=++tot] = t[p];
    t[rt].v++;
    if(l==r) return;
    if(x<=mid) insert(t[rt].ls,t[p].ls,l,mid,x);
    else insert(t[rt].rs,t[p].rs,mid+1,r,x);
}
int query(int x,int y,int l,int r,int v)
{
    if(l==r) return t[y].v - t[x].v;
    if(v<=mid) return query(t[x].ls,t[y].ls,l,mid,v);
    else return t[t[y].ls].v - t[t[x].ls].v + query(t[x].rs,t[y].rs,mid+1,r,v);
}
void build(int x)
{
    insert(rt[x],rt[fa[x]],1,m,val[x]); 
    //printf("%d %d\n",x,val[x]);
    for(int i = f[x];i+1;i=e[i].net) build(e[i].v);
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    memset(f,-1,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&fa[i]);
        if(!fa[i]) root=i;
        else insert(fa[i],i);    
    }
    scanf("%d",&m);
    for(int i=1;i<=n;i++) val[i] = m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&q[i].op,&q[i].x);
        if(q[i].op==2) val[q[i].x] = i;
        else scanf("%d %d",&q[i].y,&q[i].z);  
    }
    d[root] = 1;dfs1(root);
    dfs2(root,root);
    build(root);
    for(int i=1;i<=m;i++)
    {
        if(q[i].op==2) continue;
        int x =q[i].x, y = q[i].y ,z = q[i].z,lca=getlca(x,y);
        int num = d[x]+d[y] - 2*d[lca]+1;
        if(i-z-1<=0){printf("%d %d\n",num,0);continue;}
        int ans = query(rt[lca],rt[x],1,m,i-z-1);
        ans += query(rt[lca],rt[y],1,m,i-z-1);
        ans += (val[lca] < i-z);
        //printf("%d ",ans);
        //putchar(10);
        //printf("%d %d %d\n",t[rt[lca]].v,t[rt[x]].v,t[rt[y]].v);
        printf("%d %d\n",num,ans);
    }
    return 0;
}