题意

给一颗树，支持加点、边中加点、树链加、树链查询 的排名。

。

思路

首先做教主的魔法，然后做无处储存。

然后把两道题融合即可通过本题，随机撒点树链分块然后块内排序，查询时对整块块内二分，时间复杂度 。

可见本题只有蓝题难度。

对于加点，分成若干情况讨论然后把链重新连一下即可。

实现

但是第一次写树链分块，所以写挂了。

细节包括但不限于：

• 深度是比较难维护的，所以求 LCA 直接令一个点跳到根并标记路径，然后令另一个点去找标记，注意同在一条链上时要暴力判一下哪个比较浅（记得清空标记）。
• 连链的时候按照 为一节拆开，最后保留一节小于 的（令重链长度不小于 ），自动保证复杂度正确，然后记得下放中间的链的信息。
• 为了保证复杂度，对于散点需要维护一个下方最长链的长度，在向上找链的时候维护即可。
• 对于边中间加点有四种情况：
  1. 在链中间，这种情况先把链的信息下放下去，然后重连。
  2. 在两条链的中间，因为链是下闭上开的，所以下放下方链的信息，然后重连下方链到上方链的顶部。
  3. 在上方链的底部，直接连到上方链（这种情况当散点也行）。
  4. 在散点，这个时候要判断下方最长链的长度加上方到链上的距离，够大就从底部连上来。
• 注意边中间加点的时候，对于链信息需要提前手动下放，不然新点连好之后再下放信息会有问题。
• 在点下加点要判断上方到链上的距离，维护一下结构。
• 结点 是不在任何链中的，这个一定要注意。
• 根据实现复杂度还会有若干细节（以上是我精简代码之后仅剩的）。

关于常数

我去除了大部分的运行用时，但保留了一小部分，好让评测机知道它评测的是 N 根号 Log。

这个做法应该不卡常，我第一遍调出来就 3.7s，个人感觉询问分块然后重构的方法是比较卡常的，因为我赛后写了一份现在没过。

---

写挂的时候发现一个卡常小寄巧，对于所有非根的点总是保留第一条链不连成链（无论任何情况都不连接），让上面的点连。

然后就是对于暴力修改小于一定阈值使用插入排序。

块长调小，跑的很快，2.5s 左右。

CODE

含少量注释。

#include<cstdio>
#include<vector>
#include<random>
#include<chrono>
#include<algorithm>
using namespace std;
const int N=400010,FSIZE=1<<24,B=280;
int n,m,p[N],fa[N],up[N],in[N],dp[N],hs[N],path[N],tag[N],tmp[N];
bool v[N];
vector<int> t[N];
vector<pair<int,int>> c[N];
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF;
template<typename T>void read(T &x){
    bool f=0;
    for(x=0;48>*InF||*InF>57;*InF++=='-'&&(f=1));
    for(;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    f&&(x=-x);
}
void write(int x){
    char st[12]={},*c=st;
    for(!x&&(*OnF++=48);x;x/=10) *++c=x%10^48;
    for(;c!=st;*OnF++=*c--);
    *OnF++='\n';
}
void reset(int u){    // 下放链的信息，并删除这条链
    c[u].clear();
    if(int &i=tag[u]){
        for(int x=up[u];u!=x;u=fa[u]) p[u]+=i;
        i=0;
    }
}
void set(int x,int y){    // 将 x->y 连接成若干条链
    for(tmp[tmp[0]=1]=x;x!=y;tmp[++tmp[0]]=x=fa[x])
        if(x==in[x]) reset(x);
    for(int *i=tmp+1,*j=i,*r=tmp+tmp[0];i<r;i=j){
        int *nxt=i+B;
        if(nxt+B>r) nxt=r;
        for(;j<nxt;++j){
            up[*j]=*nxt;
            c[in[*j]=*i].emplace_back(p[*j],*j);
        }
        sort(c[*i].begin(),c[*i].end());
    }
}
int dfs(int x){    // 预处理初始撒点情况
    int re=0;
    for(int i:t[x]) if(i!=fa[x]){
        fa[i]=x;
        if(int tmp=dfs(i)){
            if(re){
                set(tmp,x);
                v[x]=1;
            }else re=tmp;
        }
        if(dp[i]>dp[hs[x]]) hs[x]=i;
    }
    dp[x]=dp[hs[x]]+1;
    return(!re&&v[x]?x:re);
}
pair<int,int> getup(int i){    // 获取到上方链的距离及编号，并维护向下最长链的长度
    for(int x,dis=0;;++dis,i=x){
        if(dp[i]>dp[hs[x=fa[i]]]) dp[x]=dp[hs[x]=i]+1;
        if(in[x]||x==1) return(make_pair(x,dis));
    }
}
void add(int u,int w){    // 点下加点
    fa[++n]=u;
    p[n]=w;
    auto m=getup(n);
    if(m.second>=B) set(n,m.first);
}
void add(int u,int v,int w){    // 边中加点
    if(fa[u]==v) swap(u,v);
    if(in[v]) reset(in[v]);    // 提前手动下放
    fa[fa[v]=++n]=u;
    p[n]=w;
    if(in[v]&&in[v]!=in[u]) return(set(in[v],u));    // 在两条链中间
    if(in[u]) return(set(u==in[u]?n:in[u],up[u]));    // 在链中间或底部
    dp[n]=dp[hs[n]=v]+1;
    auto m=getup(n);
    if(m.second+dp[n]>=B+B){
        int x=n;
        for(;hs[x];x=hs[x]);
        set(x,m.first);
    }
}
int check(int u,int v){    // 返回两结点中较浅的一个
    int x=in[u];
    for(;x!=v&&x!=u;x=fa[x]);
    return(x==v?u:v);
}
int lca(int u,int v){    // 如名
    int x=u,re=0;
    for(;!up[x]&&x>1;x=fa[x]) path[x]=1;
    for(;!up[v]&&v;v=fa[v])
        if(path[v]){
            re=v;
            break;
        }
    for(;!up[u]&&u>1;u=fa[u]) path[u]=0;
    if(re) return(re);
    for(;x>1;x=up[x]) path[in[x]]=x;
    for(;v>1;v=up[v])
        if(path[in[v]]){
            re=check(path[in[v]],v);
            break;
        }
    for(;u>1;u=up[u]) path[in[u]]=0;
    return(re?re:1);
}
void modify2(int u,int v,int w){    // 对链内（或散点）暴力修改
    int b=in[u],sz=0;
    for(;u!=v;u=fa[u],++sz) p[u]+=w;
    if(b){
        for(auto &x:c[b]) x.first=p[x.second];
        if(sz<8)
            for(auto i=c[b].begin()+1;i<c[b].end();++i)
                for(auto j=i;j>c[b].begin()&&j[-1]>*j;--j) swap(j[-1],*j);
        else sort(c[b].begin(),c[b].end());
    }
}
void modify1(int u,int x,int w){    // 修改祖先后代链
    for(;!up[u]&&u!=x;u=fa[u]) modify2(u,fa[u],w);
    for(;in[u]!=in[x];u=up[u])
        if(in[u]==u) tag[u]+=w;
        else modify2(u,up[u],w);
    modify2(u,x,w);
}
void modify(int u,int v,int w){    // 如名
    int l=lca(u,v);
    modify1(u,l,w);
    modify1(v,l,w);
    modify2(l,fa[l],w);
}
int query2(int u,int x,int w){    // 对链内（或散点）暴力询问
    int re=0;
    for(w-=tag[in[u]];u!=x;u=fa[u]) re+=p[u]>=w;
    return(re);
}
int query1(int u,int x,int w){    // 询问祖先后代链
    int re=0;
    for(;!up[u]&&u!=x;u=fa[u]) re+=p[u]>=w;
    for(;in[u]!=in[x];u=up[u])
        if(u==in[u])
            re+=c[u].end()-lower_bound(c[u].begin(),c[u].end(),make_pair(w-tag[u],0));
        else re+=query2(u,up[u],w);
    return(query2(u,x,w)+re);
}
int query(int u,int v,int w){    // 如名
    int l=lca(u,v),re=p[l]>=w-tag[in[l]];
    re+=query1(u,l,w);
    re+=query1(v,l,w);
    return(re);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(m);
    for(int i=1;i<=n;++i) read(p[i]);
    for(int i=1,x,y;i<n;++i){
        read(x);read(y);
        t[x].push_back(y);
        t[y].push_back(x);
    }
    mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());
    for(int i=v[1]=1;i<=n;i+=B) v[rnd()%n+1]=1;
    set(dfs(1),1);    // 注意手动连接最后一条传上来的链
    for(int i=0,o,x,y,w,lastans=0;i<m;++i){
        read(o);read(x);read(y);
        x^=lastans;
        y^=lastans;
        if(o!=2){
            read(w);
            w^=lastans;
            switch(o){
            case 1:add(x,y,w);break;
            case 3:modify(x,y,w);break;
            case 4:write(lastans=query(x,y,w));
            }
        }else add(x,y);
    }
    fwrite(WuF,1,OnF-WuF,stdout);
    return(0);
}