luogu P2633 Count on a tree

思路

强制在线--主席树
以1为root建主席树 (就是在树上建树，差不多)
rt[i]就是1到i的路径上的一棵树的root
其实我感觉，主席树之间的运算差不多于加减
类似lca的运算
root(1到x)+root(1到y)-root(lca）-root(fa[lca])
查询他们的第k小就OK

错误 or debug的地方

错误:运算写错了，算是思路不清晰吧 、、、
debug:和他xor的是原来的数，不是lsh之后的数字、、、

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=1e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,a[maxn],b[maxn];
struct node {
    int v,nxt;
}e[maxn<<1];
int head[maxn<<1],tot;
void add_edge(int u,int v) {
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
namespace LCA {
    int dep[maxn],st[maxn][21];
    void dfs(int u,int f) {
        for(int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if(v==f) continue;
            st[v][0]=u;
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
    int Lca(int x,int y) {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=20;i>=0;--i)
            if(dep[st[x][i]]>=dep[y]) x=st[x][i];
        if(x==y) return x;
        for(int i=20;i>=0;--i)
            if(st[x][i]!=st[y][i]) x=st[x][i],y=st[y][i];
        return st[x][0];
    }
    void init() {
        dep[1]=1;
        dfs(1,0);
        FOR(j,1,20) FOR(i,1,n)
            st[i][j]=st[st[i][j-1]][j-1]; 
    }
}
using namespace LCA;
struct edge {
    int ch[2],siz;
}t[maxn*30];
int rt[maxn],cnt;
void build(int &now,int old,int l,int r,int k) {
    now=++cnt;
    t[now]=t[old];
    t[now].siz++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) build(t[now].ch[0],t[old].ch[0],l,mid,k);
    else build(t[now].ch[1],t[old].ch[1],mid+1,r,k);
}
void DFS(int u,int f) {
    build(rt[u],rt[f],1,n,a[u]);
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(v==f) continue;
        DFS(v,u);
    }
}
int query(int a,int b,int c,int d,int l,int r,int k) {
    if(l==r) return l;
    int tot=t[t[a].ch[0]].siz+t[t[b].ch[0]].siz-t[t[c].ch[0]].siz-t[t[d].ch[0]].siz;
    int mid=(l+r)>>1;
    if(tot>=k) return query(t[a].ch[0],t[b].ch[0],t[c].ch[0],t[d].ch[0],l,mid,k);
    else return query(t[a].ch[1],t[b].ch[1],t[c].ch[1],t[d].ch[1],mid+1,r,k-tot);
}
int main() {
    //@read
    n=read(),m=read();
    FOR(i,1,n) a[i]=b[i]=read();
    FOR(i,2,n) {
        int x=read(),y=read();
        add_edge(x,y);
        add_edge(y,x);
    }
    //@lsh
    sort(b+1,b+1+n);
    int len=unique(b+1,b+1+n)-b-1;
    FOR(i,1,n) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
    //@lca_init
    init();
    //@build
    DFS(1,0);
    //@work
    int lastans=0;
    FOR(i,1,m) {
        int u=read(),v=read(),k=read();
        u=(u^lastans);
        int lca=Lca(u,v);
        lastans=b[query(rt[u],rt[v],rt[lca],rt[st[lca][0]],1,n,k)];
        cout<<lastans<<"\n"; 
    }
    return 0;
}