主席树裸题之二
练板子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
// <2588.cpp> - 08/01/16 21:55:49 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=200010; const int K=20; const int INF=1e9; struct number{ int x,id; bool operator <(const number b) const{return x<b.x;} }p[MAXN]; int n,a[MAXN]; int bt,b[MAXN],next[MAXN],to[MAXN]; inline void add(int x,int y){ next[++bt]=b[x];b[x]=bt;to[bt]=y; next[++bt]=b[y];b[y]=bt;to[bt]=x; } int f[K][MAXN],dep[MAXN]; int tot,root[MAXN],s[MAXN*20][2],val[MAXN*20]; int build(int last,int k,int l=1,int r=n){ int x=++tot; s[x][0]=s[last][0];s[x][1]=s[last][1]; val[x]=val[last]+1; if(l!=r){ int m=(l+r)>>1; if(k<=m)s[x][0]=build(s[last][0],k,l,m); else s[x][1]=build(s[last][1],k,m+1,r); } return x; } void dfs(int x){ for(int i=b[x];i;i=next[i]){ if(to[i]==f[0][x])continue; f[0][to[i]]=x; dep[to[i]]=dep[x]+1; root[to[i]]=build(root[x],a[to[i]]); dfs(to[i]); } } int lca(int x,int y){ if(dep[x]>dep[y])swap(x,y); int l=dep[y]-dep[x]; for(int i=0,now=1;i<K;i++,now<<=1) if(l&now)y=f[i][y]; if(x==y)return x; for(int i=K-1;i>=0;i--) if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y]; return f[0][x]; } int ask(int x,int y,int a,int b,int k,int l=1,int r=n){ if(l==r)return l; int m=(l+r)>>1; int lp=val[s[x][0]]+val[s[y][0]]-val[s[a][0]]-val[s[b][0]]; if(k<=lp)return ask(s[x][0],s[y][0],s[a][0],s[b][0],k,l,m); return ask(s[x][1],s[y][1],s[a][1],s[b][1],k-lp,m+1,r); } int main(){ n=gi();int m=gi(),ans=0; for(int i=1;i<=n;i++)p[i].x=gi(),p[i].id=i; sort(p+1,p+n+1); for(int i=1;i<=n;i++)a[p[i].id]=i; for(int i=1;i<n;i++)add(gi(),gi()); root[1]=build(0,a[1]); dfs(1); for(int j=1;j<K;j++) for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]]; while(m--){ int u=gi()^ans,v=gi(),k=gi(); int l=lca(u,v); ans=p[ask(root[u],root[v],root[l],root[f[0][l]],k)].x; printf("%d",ans); if(m)putchar('\n'); } return 0; } |