2588: Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit:
128 MB
Submit: 194 Solved: 62
[Submit][Status][Discuss]
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
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
8
9
105
7
HINT
HINT：
N,M<=100000
暴力自重。。。
随着主席树的出现……这类问题以沦为经典问题……
每个节点维护他到根路径上的权值线段树，然后减出来就好了……
虽然代码略长，但是很好写……
Count on a tree II我不会，求拯救
program bzoj2588;
var
u,v,tot,all,ans,n,m,i,j,k:longint;
h,ent,root,new,a:array [0..100001] of longint;
next,point:array [0..200001] of longint;
fa:array [0..20,0..100001] of longint;
left,right,sum:array [0..3000001] of longint;
procedure swap (var a,b:longint);
begin
if a=b then exit;
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
procedure connect (u,v:longint);
begin
inc(tot);
point[tot]:=v;
next[tot]:=root[u];
root[u]:=tot;
end;
procedure insert (x,now,last:longint);
var
l,r,mid:longint;
begin
l:=1;
r:=all;
repeat
sum[now]:=sum[last]+1;
if l=r then break;
mid:=(l+r) div 2;
if x<=mid then
begin
inc(tot);
left[now]:=tot;
right[now]:=right[last];
now:=tot;
last:=left[last];
r:=mid;
end
else
begin
left[now]:=left[last];
inc(tot);
right[now]:=tot;
now:=tot;
last:=right[last];
l:=mid+1;
end;
until false;
end;
function find (x,x1,x2,x3,x4:longint):longint;
var
l,r,mid:longint;
begin
l:=1;
r:=all;
while l<>r do
begin
mid:=(l+r) div 2;
if sum[left[x1]]+sum[left[x2]]-sum[left[x3]]-sum[left[x4]]>=x then
begin
r:=mid;
x1:=left[x1];
x2:=left[x2];
x3:=left[x3];
x4:=left[x4];
end
else
begin
x:=x-(sum[left[x1]]+sum[left[x2]]-sum[left[x3]]-sum[left[x4]]);
l:=mid+1;
x1:=right[x1];
x2:=right[x2];
x3:=right[x3];
x4:=right[x4];
end;
end;
exit(l);
end;
procedure build (s,e,now:longint);
var
mid:longint;
begin
if s=e then exit;
mid:=(s+e) div 2;
inc(tot);
left[now]:=tot;
build(s,mid,tot);
inc(tot);
right[now]:=tot;
build(mid+1,e,tot);
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=new[(s+e) div 2];
while i<=j do
begin
while new[i]<k do inc(i);
while new[j]>k do dec(j);
if i>j then break;
swap(new[i],new[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
function convert (x:longint):longint;
var
s,e,mid:longint;
begin
s:=1;
e:=all;
while s<>e do
begin
mid:=(s+e) div 2;
if new[mid]<x then s:=mid+1
else e:=mid;
end;
exit(s);
end;
procedure dfs (now,high:longint);
var
i:longint;
begin
h[now]:=high;
i:=0;
while fa[i,fa[i,now]]<>0 do
begin
fa[i+1,now]:=fa[i,fa[i,now]];
inc(i);
end;
inc(tot);
ent[now]:=tot;
insert(a[now],tot,ent[fa[0,now]]);
i:=root[now];
while i<>0 do
begin
if point[i]<>fa[0,now] then
begin
fa[0,point[i]]:=now;
dfs(point[i],high+1);
end;
i:=next[i];
end;
end;
function lca (a,b:longint):longint;
var
i:longint;
begin
if h[a]>h[b] then swap(a,b);
while h[a]<>h[b] do
b:=fa[trunc(ln(h[b]-h[a])/ln(2)),b];
if a=b then exit(a);
i:=20;
repeat
if fa[0,a]=fa[0,b] then exit(fa[0,a]);
while fa[i,a]=fa[i,b] do dec(i);
a:=fa[i,a];
b:=fa[i,b];
until false;
end;
begin
read(n,m);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
new[i]:=a[i];
for i:=1 to n-1 do
begin
read(u,v);
connect(u,v);
connect(v,u);
end;
qsort(1,n);
i:=1;
while i<=n do
begin
inc(all);
new[all]:=new[i];
while (i<=n)and(new[i]=new[all]) do inc(i);
end;
for i:=1 to n do
a[i]:=convert(a[i]);
tot:=0;
build(1,all,0);
dfs(1,1);
for i:=1 to m do
begin
read(u,v,k);
u:=u xor ans;
j:=lca(u,v);
ans:=new[find(k,ent[u],ent[v],ent[j],ent[fa[0,j]])];
writeln(ans);
end;
end.