题目描述
给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。
输入输出格式
输入格式：
第一行两个整数N,M。
第二行有N个整数，其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。
最后M行每行两个整数(u,v,k)，表示一组询问。
输出格式：
M行，表示每个询问的答案。
输入输出样例
输入样例#1： 复制
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
输出样例#1： 复制
2
8
9
105
7
说明
HINT：
N,M<=100000
暴力自重。。。
来源：bzoj2588 Spoj10628.
本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。
树上第$k$大问题
做法比较套路
首先对权值离散化。
然后对每个节点建主席树，从父亲那里拷贝历史版本
求LCA的话用树剖，顺便可以建主席树。
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=*1e6+;
const int INF=1e8+;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=nc();}
while(c>=''&&c<=''){x=x*+c-'';c=nc();}
return x*f;
}
struct Edge
{
int u,v,nxt;
}E[MAXN];
int head[MAXN];
int num=;
inline void AddEdge(int x, int y)
{
E[num].u = x;
E[num].v = y;
E[num].nxt = head[x];
head[x] = num++;
}
int a[MAXN], b[MAXN], N, M, root[MAXN], totnum;
int deep[MAXN], son[MAXN], top[MAXN], fa[MAXN], tot[MAXN];
struct node
{
int ls, rs, w;
}T[MAXN];
void Insert(int pre,int &now,int ll,int rr,int val)
{
now=++totnum;
T[now].ls=T[pre].ls;T[now].rs=T[pre].rs;
T[now].w=T[pre].w+;
if(ll==rr) return ;
int mid=ll+rr>>;
if(val<=mid) Insert(T[pre].ls,T[now].ls,ll,mid,val);
else Insert(T[pre].rs,T[now].rs,mid+,rr,val);
}
void dfs1(int now, int f)
{
fa[now] = f;
Insert(root[f],root[now],,N,a[now]);
tot[now] = ;
int maxson=-;
for(int i = head[now]; i != -; i = E[i].nxt)
{
if(deep[E[i].v] == && E[i].v != f)
{
deep[E[i].v] = deep[now] + ;
dfs1(E[i].v, now);
tot[now] += tot[E[i].v];
if(tot[E[i].v]>maxson) maxson = tot[E[i].v],son[now] = E[i].v;
}
}
}
void dfs2(int now, int topf)
{
top[now] = topf;
if(!son[now]) return ;
dfs2(son[now], topf);
for(int i = head[now]; i != -; i=E[i].nxt)
if(E[i].v != son[now] && E[i].v != fa[now])
dfs2(E[i].v, E[i].v);
}
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 x;
}
int Query(int x, int y, int lca, int falca, int ll, int rr, int k)
{
if(ll==rr) return ll;
int used=T[T[x].ls].w + T[T[y].ls].w - T[T[lca].ls].w - T[T[falca].ls].w;
int mid=ll+rr>>;
if(k<=used) return Query(T[x].ls, T[y].ls, T[lca].ls, T[falca].ls, ll, mid, k);
else return Query(T[x].rs, T[y].rs, T[lca].rs, T[falca].rs, mid+, rr, k-used);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
memset(head,-,sizeof(head));
N = read(); M = read();
for(int i = ; i<=N; i++) a[i] = b[i] = read();
sort(b+, b+N+);
int num = unique(b, b+N+) - b - ;
for(int i = ; i<=N; i++) a[i]=lower_bound(b, b+N, a[i]) - b;
for(int i=; i<=N-; i++)
{
int x=read(), y=read();
AddEdge(x, y);
AddEdge(y, x);
}
deep[] = ;
dfs1(, );
dfs2(,);
int lastans=;
while(M--)
{
int x=read(),y=read(),k=read();
x=x^lastans;
int lca=LCA(x,y);
lastans=b[Query(root[x], root[y], root[lca], root[fa[lca]],,N,k)];
printf("%d\n",lastans);
}
return ;
}