Written with StackEdit.
Description
给定一棵(N)个节点的树，每个点有一个权值，对于(M)个询问((u,v,k))，你需要回答(u) xor (lastans)和(v)这两个节点间第(K)小的点权。其中(lastans)是上一个询问的答案，初始为(0)，即第一个询问的(u)是明文。
Input
第一行两个整数(N,M)。
第二行有(N)个整数，其中第(i)个整数表示点(i)的权值。
后面(N-1)行每行两个整数((x,y))，表示点(x)到点(y)有一条边。
最后(M)行每行两个整数((u,v,k))，表示一组询问。
Output
(M)行，表示每个询问的答案.
Sample Input
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2
Sample Output
2
8
9
105
7
HINT
(N,M<=100000).
Solution
- 将区间求第(k)小搬到了树上,询问时强制在线,仍是主席树的基本操作.
- 对比树上差分时的处理方式,不难得出(u)到(v)的路径对应的线段树应是(T[u]+T[v]-T[lca]-T[fa[lca]].)
- 需要特别注意的是,初始化时应该根据(dfs)序插入各个点.
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int MAXN=1e5+10;
int ecnt=0,head[MAXN],nx[MAXN<<1],to[MAXN<<1];
int fa[MAXN],top[MAXN],mxson[MAXN],siz[MAXN],dep[MAXN];
int n,m;
inline void addedge(int u,int v)
{
++ecnt;
nx[ecnt]=head[u];
to[ecnt]=v;
head[u]=ecnt;
}
int rt[MAXN];
struct PreSegTree{
struct node{
int lson,rson,cnt;
}Tree[MAXN*20];
int idx;
PreSegTree()
{
idx=0;
}
int BuildTree(int l,int r)
{
int cur=++idx;
Tree[cur].cnt=0;
if(l<r)
{
int mid=(l+r)>>1;
Tree[cur].lson=BuildTree(l,mid);
Tree[cur].rson=BuildTree(mid+1,r);
}
return cur;
}
void update(int &cur,int last,int l,int r,int pos)
{
cur=++idx;
Tree[cur]=Tree[last];
++Tree[cur].cnt;
if(l==r)
return;
int mid=(l+r)>>1;
if(pos<=mid)
update(Tree[cur].lson,Tree[last].lson,l,mid,pos);
else
update(Tree[cur].rson,Tree[last].rson,mid+1,r,pos);
}
int query(int u,int v,int lca,int lcafa,int l,int r,int k)
{
if(l==r)
return l;
int p=Tree[Tree[u].lson].cnt+Tree[Tree[v].lson].cnt-Tree[Tree[lca].lson].cnt-Tree[Tree[lcafa].lson].cnt;
int mid=(l+r)>>1;
if(p>=k)
return query(Tree[u].lson,Tree[v].lson,Tree[lca].lson,Tree[lcafa].lson,l,mid,k);
else
return query(Tree[u].rson,Tree[v].rson,Tree[lca].rson,Tree[lcafa].rson,mid+1,r,k-p);
}
}T;
int a[MAXN],b[MAXN],Siz;
void dfs1(int u,int pre)
{
T.update(rt[u],rt[pre],1,Siz,a[u]);
dep[u]=dep[pre]+1;
siz[u]=1;
fa[u]=pre;
for(int i=head[u];i;i=nx[i])
{
int v=to[i];
if(v!=pre)
{
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[mxson[u]])
mxson[u]=v;
}
}
}
void dfs2(int u,int tp)
{
top[u]=tp;
if(mxson[u])
dfs2(mxson[u],tp);
for(int i=head[u];i;i=nx[i])
{
int v=to[i];
if(v!=fa[u] && v!=mxson[u])
dfs2(v,v);
}
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int lastans=0;
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
b[i]=a[i]=read();
sort(b+1,b+1+n);
Siz=unique(b+1,b+1+n)-(b+1);
rt[0]=T.BuildTree(1,Siz);
for(int i=1;i<=n;++i)
{
a[i]=lower_bound(b+1,b+1+Siz,a[i])-b;
}
for(int i=1;i<n;++i)
{
int u=read();
int v=read();
addedge(u,v);
addedge(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;++i)
{
int u=read(),v=read();
int k=read();
u^=lastans;
int lca=LCA(u,v);
lastans=T.query(rt[u],rt[v],rt[lca],rt[fa[lca]],1,Siz,k);
lastans=b[lastans];
printf("%d
",lastans);
}
return 0;
}