題目描述
給定一棵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分鐘完成資料制作。
題解:主席樹上樹
就是把根節點到該點的鍊用主席樹維護
查詢x到y的鍊上k小值就是将鍊拆成(1~x)+(1~y)-(1~lca(x,y))-(1~fa(lca(x,y))
顯然這種東西是可以主席樹維護的,然後就可以A掉了
代碼如下:
#include<bits/stdc++.h>
#define lson tr[now].l
#define rson tr[now].r
using namespace std;
struct tree
{
int l,r,sum;
}tr[5000050];
int a[100010],b[100010],n,m,cnt,f[100010][18],rt[100010],deep[100010];
vector<int> g[100010];
int init()
{
map<int,int> m;
sort(b+1,b+n+1);
int tot=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=tot;i++)
{
m[b[i]]=i;
}
for(int i=1;i<=n;i++)
{
a[i]=m[a[i]];
}
}
int push_up(int now)
{
tr[now].sum=tr[lson].sum+tr[rson].sum;
}
int insert(int &now,int fa,int l,int r,int pos)
{
if(l==r)
{
now=++cnt;
tr[now].sum=tr[fa].sum+1;
return 0;
}
int mid=(l+r)>>1;
now=++cnt;
tr[now].sum=tr[fa].sum+1;
if(pos<=mid)
{
insert(lson,tr[fa].l,l,mid,pos);
tr[now].r=tr[fa].r;
}
else
{
insert(rson,tr[fa].r,mid+1,r,pos);
tr[now].l=tr[fa].l;
}
push_up(now);
}
int query(int t1,int t2,int t3,int t4,int l,int r,int k)
{
if(l==r)
{
return l;
}
int cnt=tr[tr[t1].l].sum+tr[tr[t2].l].sum-tr[tr[t3].l].sum-tr[tr[t4].l].sum;
int mid=(l+r)>>1;
if(cnt>=k)
{
query(tr[t1].l,tr[t2].l,tr[t3].l,tr[t4].l,l,mid,k);
}
else
{
query(tr[t1].r,tr[t2].r,tr[t3].r,tr[t4].r,mid+1,r,k-cnt);
}
}
int dfs(int now,int ff,int dep)
{
deep[now]=dep;
f[now][0]=ff;
for(int i=1;i<=17;i++) f[now][i]=f[f[now][i-1]][i-1];
insert(rt[now],rt[ff],1,100000,a[now]);
for(int i=0;i<g[now].size();i++)
{
if(g[now][i]==ff) continue;
dfs(g[now][i],now,dep+1);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=17;i>=0;i--)
{
if(deep[f[x][i]]>=deep[y]) x=f[x][i];
}
if(x==y) return x;
for(int i=17;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
init();
int from,to,k;
for(int i=1;i<n;i++)
{
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0,1);
int ans=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&from,&to,&k);
from^=ans;
int l=lca(from,to);
int fl=f[l][0];
printf("%d\n",ans=b[query(rt[from],rt[to],rt[l],rt[fl],1,100000,k)]);
}
}