[SCOI2015]情报传递

摘要

有趣的树剖+主席树题

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

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

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

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

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

即树上动态操作:

  • 修改点权(初始时点权为INF)
  • 查询路径 上点权在值域 中的点的个数
  • 查询LCA

我们记录每个情报员开始传递情报的那一天(初始时为INF),注意到,对于第 天的风险情报员,我们只需要查询点权在 的情报员有多少个即可。所以我们可以直接读入整个询问建立静态主席树,避免了动态修改的过程。

通过建立树上主席树,每个结点继承父节点的版本,然后查询的时候减掉 的部分即可。总复杂度 .

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,root;

struct qxx{int nex,t;};
qxx e[N];
int h[N],cnt;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

namespace TRD{//树链剖分
int par[N],sz[N],dep[N];
int hvs[N],top[N];
int szdfs(int u,int p,int deep){
dep[u]=deep,sz[u]=1,par[u]=p;
for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;//有向树
if(v!=p)sz[u]+=szdfs(v,u,deep+1);
}
return sz[u];
}
void dedfs(int u,int p,int topp){
top[u]=topp;
for(int i=h[u],mxz=0;i;i=e[i].nex){const int &v=e[i].t;
if(v!=p&&sz[v]>mxz)mxz=sz[v],hvs[u]=v;
}
if(!hvs[u])return;
dedfs(hvs[u],u,topp);
for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
if(v!=p&&v!=hvs[u])dedfs(v,u,v);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=par[top[x]];
}
return dep[x]<dep[y]?x:y;
}
}
int q;
namespace CMT{//主席树
const int CMT_SZ=18*(1<<18);
int val[N],tot;
int rt[CMT_SZ],lc[CMT_SZ],rc[CMT_SZ],cnt[CMT_SZ];//cnt:当前值域区间内数的个数
int build(int l,int r){//建立版本0
int u=++tot,mid=(l+r)>>1;
if(l<r)lc[u]=build(l,mid),rc[u]=build(mid+1,r);
return u;
}
int modify(int u,int v,int l=1,int r=q+1){//从旧版本中的u结点修改得来
int u2=++tot,mid=(l+r)>>1;
if(l==r)return cnt[u2]=cnt[u]+1,u2;
if(v<=mid)lc[u2]=modify(lc[u],v,l,mid),rc[u2]=rc[u];
else lc[u2]=lc[u],rc[u2]=modify(rc[u],v,mid+1,r);
return cnt[u2]=cnt[u]+1,u2;
}
void dfsbuild(int u,int p){//u从p继承而来
rt[u]=modify(rt[p],val[u]);
for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
if(v!=p)dfsbuild(v,u);
}
}
int query(int u,int L,int R,int l=1,int r=q+1){//查询值域[L,R]内的数的个数
if((L<=l&&r<=R)||!cnt[u])return cnt[u];
int mid=(l+r)>>1,res=0;
if(L<=mid)res+=query(lc[u],L,R,l,mid);
if(mid<R)res+=query(rc[u],L,R,mid+1,r);
return res;
}
int qnode(int x,int L,int R){
return query(rt[x],L,R);
}
}
int x[N],y[N],c[N],t[N],k[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int p;
scanf("%d",&p);
if(p==0)root=i;
else add_path(p,i);
}
TRD::szdfs(root,0,1);
TRD::dedfs(root,root,root);
scanf("%d",&q);
for(int i=1;i<=n;i++)CMT::val[i]=q+1;//初始化为最大值
for(int i=1;i<=q;i++){
scanf("%d",&k[i]);
if(k[i]==1)scanf("%d%d%d",&x[i],&y[i],&c[i]);
else scanf("%d",&t[i]),CMT::val[t[i]]=i;//情报员t[i]在第i天开始收集情报
}
CMT::rt[0]=CMT::build(1,q+1);
CMT::dfsbuild(root,0);//从0继承
//开始处理询问
for(int i=1;i<=q;i++){
if(k[i]!=1)continue;
int z=TRD::lca(x[i],y[i]);
int a=CMT::qnode(x[i],0,i-c[i]-1)+CMT::qnode(y[i],0,i-c[i]-1)
-CMT::qnode(z,0,i-c[i]-1)-CMT::qnode(TRD::par[z],0,i-c[i]-1);
int b=TRD::dep[x[i]]+TRD::dep[y[i]]
-TRD::dep[z]-TRD::dep[TRD::par[z]];
printf("%d %d\n",b,a);
}
return 0;
}
/*
* 先读取所有询问建立静态主席树;
* 第i天危险值为C,即查询i-c<x<i的值的个数,那么两次查询两边即可;
* 初始化每个人的权值为INF;
* 写一个树剖来求LCA;
* BUG#1: qnode在主函数里调用的时候,参数给错
* BUG#2: CMT内存没开够
*/