正文
BZOJ2588：Count on a tree——题解
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
http://www.lydsy.com/JudgeOnline/problem.php?id=2588
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)，表示一组询问。OutputM行，表示每个询问的答案。最后一个询问不输出换行符
Sample Input8 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 2Sample Output2
8
9
105
7
给定一棵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)，表示一组询问。
OutputM行，表示每个询问的答案。最后一个询问不输出换行符
Sample Input8 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 2Sample Output2
8
9
105
7
M行，表示每个询问的答案。最后一个询问不输出换行符
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 Output2
8
9
105
7
8
9
105
7
——————————————————————————
sb题（debug一晚上并且跨年的sb题）
没有考虑到根节点的爸爸是0所以犯了个sb错误。
直接考虑向根节点的每一条链上节点建主席树。
这样我们的delta就为sum[a]+sum[b]-sum[LCA(a,b)]-sum[father[lca(a,b)]]
#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
inline ll read(){
ll X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct tree{
int l;
int r;
int sum;
}tr[N*];
struct node{
int to;
int nxt;
}edge[N*];
int a[N],b[N],rt[N],n,m,q,pool;
int dep[N]={},anc[N][]={};
int cnt=,head[N*]={};
inline void add(int u,int v){
cnt++;
edge[cnt].to=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
return;
}
inline void LSH(){
sort(b+,b+m+);
m=unique(b+,b+m+)-b-;
for(int i=;i<=n;i++){
a[i]=lower_bound(b+,b+m+,a[i])-b;
}
return;
}
inline void insert(int y,int &x,int l,int r,int p){
tr[x=++pool]=tr[y];tr[x].sum++;
if(l==r)return;
int mid=(l+r)>>;
if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p);
else insert(tr[y].r,tr[x].r,mid+,r,p);
return;
}
inline int query(int nl,int nr,int nm,int nfm,int l,int r,int k){
if(l==r)return l;
int delta=tr[tr[nl].l].sum+tr[tr[nr].l].sum-tr[tr[nm].l].sum-tr[tr[nfm].l].sum;
int mid=(l+r)>>;
if(delta>=k)return query(tr[nl].l,tr[nr].l,tr[nm].l,tr[nfm].l,l,mid,k);
else return query(tr[nl].r,tr[nr].r,tr[nm].r,tr[nfm].r,mid+,r,k-delta);
}
void dfs(int i){
dep[i]=dep[anc[i][]]+;
insert(rt[anc[i][]],rt[i],,m,a[i]);
for(int j=head[i];j;j=edge[j].nxt){
int k=edge[j].to;
if(k!=anc[i][]){
anc[k][]=i;
dfs(k);
}
}
return;
}
int LCA(int i,int j){
if(dep[i]<dep[j])swap(i,j);
for(int k=;k>=;k--){
if(dep[anc[i][k]]>=dep[j])i=anc[i][k];
}
if(i==j)return i;
for(int k=;k>=;k--){
if(anc[i][k]!=anc[j][k])i=anc[i][k],j=anc[j][k];
}
return anc[i][];
}
void LCAinit(){
for(int i=;i<=n;i++){
int u=read();
int v=read();
add(u,v);
add(v,u);
}
dfs();
for(int j=;j<=;j++){
for(int i=;i<=n;i++){
anc[i][j]=anc[anc[i][j-]][j-];
}
}
return;
}
int main(){
n=read();
q=read();
for(int i=;i<=n;i++)a[i]=b[++m]=read();
LSH();
LCAinit();
int pre=;
for(int i=;i<=q;i++){
int u=read()^pre,v=read(),k=read();
int t=LCA(u,v);int ft=anc[t][];
printf("%d",pre=b[query(rt[u],rt[v],rt[t],rt[ft],,m,k)]);
if(i<q)putchar('\n');
}
return ;
}
