P4216 情报传递 题解

· · 题解

首先进行题意转换，假设当前操作的时间是第 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];
        }
    }
}

马蜂丑轻喷。