Count on a tree

学习了主席树后被虐了。。。

传送门

题意：

求静态树上第k小，强制在线。

做法：

刚学了主席树开始做这题，一开始以为是树剖还在想零零碎碎的区间怎么合并，但实际上用树上差分就好了。

在树上建主席树，把a结点基于fa[a]结点建树。

查询的时候用$sum[x]+sum[y]-sum[lca]-sum[fa[lca]]$判断

#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 100001
using namespace std;
struct node{
    int h,z;
}a[maxn];
struct edge{
    int next,to;
}w[maxn<<1];
int head[maxn*25],edg,cnt,top[100010*25],sum[maxn*25];
int c[maxn],hs[maxn],size[maxn],ls[maxn*25],n,m;
int b[maxn],deep[maxn],fa[maxn],rs[maxn*25],bs[maxn];
inline bool cmp(node c,node d){
    return c.z<d.z;
}
inline void add(int x,int y){
    w[++edg].next=head[x];
    w[edg].to=y; head[x]=edg;
}
void built(int &rt,int l,int r){
    rt=++cnt;
    if (l==r) return;
    int mid=(l+r)>>1;
    built(ls[rt],l,mid);
    built(rs[rt],mid+1,r);
}
int build(int rt,int l,int r,int p){
    int t=++cnt;
    ls[t]=ls[rt],rs[t]=rs[rt],sum[t]=sum[rt]+1;
    if (l==r) return t;  int mid=(l+r)>>1;
    if (p<=mid) ls[t]=build(ls[rt],l,mid,p);
    else rs[t]=build(rs[rt],mid+1,r,p);
    return t;
}
//void build(int rt,int &now,int l,int r,int p){
//	now=++cnt; sum[now]=sum[rt]+1;
//	if (l==r) return;
//	int mid=(l+r)>>1;
//	if (p<=mid) rs[now]=rs[rt],build(ls[rt],ls[now],l,mid,p);
//	else ls[now]=ls[rt],build(rs[rt],rs[now],mid+1,r,p);
//}
void dfs1(int x,int da){
    fa[x]=da; size[x]=1;
    bs[x]=build(bs[da],1,b[a[n].h],b[x]);
    for (int i=head[x]; i; i=w[i].next){
        if (w[i].to!=da){
            deep[w[i].to]=deep[x]+1;
            dfs1(w[i].to,x);
            size[x]+=size[w[i].to];
            if (size[w[i].to]>size[hs[x]]) hs[x]=w[i].to;
        }
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    if (hs[x]) dfs2(hs[x],tp);
    for (int i=head[x]; i; i=w[i].next)
        if (w[i].to!=fa[x]&&w[i].to!=hs[x])
            dfs2(w[i].to,w[i].to);
}
inline int lca(int x,int y){
    while (top[x]!=top[y]){
        if (deep[top[x]]<deep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if (deep[x]<deep[y]) swap(x,y);
    return y;
}
int query(int x,int y,int da,int gr,int l,int r,int k){
    if (l>=r) return l; int mid=(l+r)>>1;
    int num=sum[ls[x]]+sum[ls[y]]-sum[ls[da]]-sum[ls[gr]];
    if (num>=k) return query(ls[x],ls[y],ls[da],ls[gr],l,mid,k);
    else return query(rs[x],rs[y],rs[da],rs[gr],mid+1,r,k-num);
}
int main(){
    int last=0,x,y,z;
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++){
        scanf("%d",&a[i].z);
        a[i].h=i;
    }
    sort(a+1,a+n+1,cmp); a[0].z=-1;
    for (int i=1; i<=n; i++){
        b[a[i].h]=b[a[i-1].h];
        if (a[i].z!=a[i-1].z) b[a[i].h]++;
        c[b[a[i].h]]=a[i].z;
    }
    for (int i=1; i<=n-1; i++){
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
//	built(bs[0],1,b[a[n].h]);
    deep[1]=1; dfs1(1,0); dfs2(1,1);
    while (m--){
        scanf("%d%d%d",&x,&y,&z);
        x^=last; int lc=lca(x,y);
        last=c[query(bs[x],bs[y],bs[lc],bs[fa[lc]],1,b[a[n].h],z)];
        printf("%d\n",last);
    }
    return 0;
}

改天写一下主席树学习笔记 不会咕