[CTSC2008]网络管理

洛咕

题意:带点权修改的 询问树上路径第\(K\)大.\(n,Q<=80000.\)

分析:如果不是树上路径其实就是整体二分的板子题,所以我们只要考虑如何将树上路径转变为区间序列,有一个比较常见的套路,树链剖分+\(dfn\)序.

真的是一道码农题和恶心的细节题,调了一上午,就是因为一个\(y\)写成了\(z\).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=80005;
int n,Q,tot,tim,order,t[N],ans[N],c[N];
int dep[N],dfn[N],size[N],son[N],f[N],top[N];
int cnt,head[N],nxt[N<<1],to[N<<1];
inline void add(int a,int b){nxt[++cnt]=head[a];head[a]=cnt;to[cnt]=b;}
struct node{int x,y,z,opt,id;}q[N<<2],ql[N<<2],qr[N<<2];
inline void dfs1(int u,int fa){
    f[u]=fa;dep[u]=dep[fa]+1;size[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        dfs1(v,u);size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}
inline void dfs2(int u,int fa){
    dfn[u]=++order;
    if(son[u]){
        top[son[u]]=top[u];
        dfs2(son[u],u);
    }
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa||v==son[u])continue;
        top[v]=v;dfs2(v,u);
    }
}
inline int LCA(int x,int y){
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=f[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
inline void update(int x,int v){for(;x<=n;x+=x&-x)c[x]+=v;}
inline int ask(int x){int res=0;for(;x;x-=x&-x)res+=c[x];return res;}
inline int query(int x,int y){
    int res=0;
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res+=ask(dfn[x])-ask(dfn[top[x]]-1);
        x=f[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    res+=ask(dfn[x])-ask(dfn[y]-1);
    return res;
}
inline void solve(int l,int r,int st,int ed){
    if(st>ed)return;
    if(l==r){
        for(int i=st;i<=ed;++i)if(q[i].opt>=1)ans[q[i].opt]=l;
        return;
    }
    int mid=(l+r)>>1,lt=0,rt=0;
    for(int i=st;i<=ed;++i){
        if(q[i].opt==-1){//删除操作
            if(q[i].y<=mid)update(q[i].x,-1),ql[++lt]=q[i];
            else qr[++rt]=q[i];
        }
        if(!q[i].opt){//赋值操作
            if(q[i].y<=mid)update(q[i].x,1),ql[++lt]=q[i];
            else qr[++rt]=q[i];
        }
        if(q[i].opt>=1){//询问操作
            int sum=query(q[i].x,q[i].y);
            if(sum>=q[i].z)ql[++lt]=q[i];
            else q[i].z-=sum,qr[++rt]=q[i];
        }
    }
    for(int i=ed;i>=st;--i){
        if(q[i].opt==-1&&q[i].y<=mid)update(q[i].x,1);
        if(!q[i].opt&&q[i].y<=mid)update(q[i].x,-1);
    }
    for(int i=1;i<=lt;++i)q[st+i-1]=ql[i];
    for(int i=1;i<=rt;++i)q[lt+st+i-1]=qr[i];
    solve(l,mid,st,st+lt-1);solve(mid+1,r,st+lt,ed);
}
int main(){
    n=read();Q=read();for(int i=1;i<=n;++i)t[i]=read();
    for(int i=1,a,b;i<n;++i)a=read(),b=read(),add(a,b),add(b,a);
    dfs1(1,0);dfs2(1,1);//两次dfs树链剖分的板子
    for(int i=1;i<=n;++i)q[++tot].opt=0,q[tot].x=dfn[i],q[tot].y=t[i];//老套路:把初始赋值操作也当做一次修改操作
    for(int i=1;i<=Q;++i){
        int k=read(),x=read(),y=read();
        if(k){
            int len=dep[x]+dep[y]-2*dep[LCA(x,y)]+1;//查询路径上的点数
            if(k>len)k=1e8;//如果路径上没有K个点,特判
            else k=len-k+1;//将第K大转化为第K小
            q[++tot].opt=++tim;q[tot].x=x;q[tot].y=y;q[tot].z=k;
        }
        else{
            q[++tot].opt=-1;q[tot].x=dfn[x];q[tot].y=t[x];
            t[x]=y;
            q[++tot].opt=0;q[tot].x=dfn[x];q[tot].y=t[x];
        }//老套路:把修改操作拆成一次删除和一次赋值操作
    }
    solve(0,1e8,1,tot);//题目给定了值域为1e8
    for(int i=1;i<=tim;++i){
        if(ans[i]==1e8)puts("invalid request!");
        else printf("%d\n",ans[i]);
    }
    return 0;
}