SCOI2015 情报传递主席树+LCA-526互联

哈哈哈哈老婆我有出息了，犬犬第一次从思路到代码都是自己一发切了紫题呢~

好了一眼数据结构。

考虑如何转化第i个时刻有威胁的情报员，若能产生威胁

则说明他们至少在i-c-1这个时刻"出生"

也就是转化为在权值线段树上查询[1,i-c-1]有多少个人。

启发了我们可以先把未来的情报员都弄下来，再记一个他们的生日，放到权值线段树上。

可是它是树上问题哎，怎么弄？

答：求个LCA，经典树上差分。

主席树的部分就是相当于把树拍成链，每个点在父亲节点的基础上，继续单点更新（或者不需要），维护从该点到根节点一共有多少人。

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=2e5+5;
const int N=maxn<<5;
int u[maxn];
struct tree{
    int ls,rs,sum;
}t[N];
int idx,rt[N];
vector<int>e[maxn];
struct query{
    int k,x,y,c;
}query[maxn];
int n,Q,people[maxn],dep[maxn],f[maxn][20],lg[maxn];
int update(int p,int pos,int l=1,int r=maxn){
    int q=++idx;
    t[q]=t[p];
    t[q].sum++;
    if(l==r){
        return q;
    }
    int mid=l+r>>1;
    if(pos<=mid) t[q].ls=update(t[p].ls,pos,l,mid);
    else t[q].rs=update(t[p].rs,pos,mid+1,r);
    return q;
}
void dfs(int u,int fa){
    // lca 
    if(people[u]){
        rt[u]=update(rt[fa],people[u]);
        //cout<<t[rt[u]].sum<<endl;
    }
    else {
        rt[u]=rt[fa];
    }
    
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=lg[dep[u]];i++){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    
    for(int i=0;i<e[u].size();i++){
        int to=e[u][i];
        if(to==fa) continue;
        dfs(to,u);
    }
}
int getLca(int u, int v) {
    
    if (dep[u]<dep[v]) swap(u,v);
    for (int j=lg[dep[u]];j>=0;j--) {//让u，v到达同一高度
        if (dep[u]-(1<<j)>=dep[v]) {
            u=f[u][j];
        }
    }
    if (u==v) return u;
    for (int j=lg[dep[u]];j>=0;j--) {
        if (f[u][j]!=f[v][j]) {
            u=f[u][j];
            v=f[v][j];
        }
    }
    return f[u][0];
}
void init(int n){
    for(int i=2;i<=n;i++){
        lg[i]=lg[i/2]+1;
    }
}
int ask(int x,int y,int lca,int fa,int ql,int qr,int l=1,int r=maxn){
    if(ql>qr) return 0;
    //cout<<"l: "<<l<<" r: "<<qr<<" "<<t[x].sum<<" "<<t[y].sum<<" "<<t[lca].sum<<endl;
    if(ql<=l&&r<=qr) {
        /*cout<<"at [l,r]"<<ql<<" "<<qr<<" "<<l<<" "<<r<<endl;
        cout<<"return: "<<endl;
        cout<<"tx: "<<t[x].sum<<endl;
        cout<<"ty: "<<t[y].sum<<endl;
        cout<<"lca: "<<t[lca].sum<<endl;
        cout<<"fa: "<<t[fa].sum<<endl;
        cout<<"tot: "<<t[x].sum+t[y].sum-t[lca].sum-t[fa].sum<<endl;
        */
        return t[x].sum+t[y].sum-t[lca].sum-t[fa].sum;
    }
    int ans=0,mid=l+r>>1;
    if(ql<=mid) ans+=ask(t[x].ls,t[y].ls,t[lca].ls,t[fa].ls,ql,qr,l,mid);
    if(qr>mid) ans+=ask(t[x].rs,t[y].rs,t[lca].rs,t[fa].rs,ql,qr,mid+1,r); 
    //cout<<"l: "<<l<<" r: "<<r<<" "<<ans<<endl;
    return ans;
}
int main(){
    //freopen("lys.in","r",stdin);
    fastio;
    cin>>n;
    init(n);
    int root;
    for(int i=1;i<=n;i++){
        cin>>u[i];
        if(u[i]==0) root=i;
        else e[u[i]].push_back(i);
    }
    cin>>Q;
    for(int i=1;i<=Q;i++){
        cin>>query[i].k;
        if(query[i].k==1){
            cin>>query[i].x>>query[i].y>>query[i].c;
        }
        else {
            int ti;cin>>ti;
            people[ti]=i;// i-th day ti is actived
        }
    }
    dfs(root,0);
    for(int i=1;i<=Q;i++){
        if(query[i].k==2) continue;
        int lca=getLca(query[i].x,query[i].y);
        int fa_lca=f[lca][0];
        //cout<<":: q"<<query[i].x<<" "<<query[i].y<<" "<<lca<<" "<<fa_lca<<endl;
        //cout<<"birth-day before: "<<i-query[i].c-1<<endl;
        cout<<dep[query[i].x]+dep[query[i].y]-dep[lca]-dep[fa_lca]<<" "<<ask(rt[query[i].x],rt[query[i].y],rt[lca],rt[fa_lca],1,i-query[i].c-1)<<endl;// Birth < i-c-1
    }
}