2588: Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit: 128 MB
Submit: 2872 Solved: 650
[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
暴力自重。。。
Source
不会做被神犇喷了。。。
树上主席树。。感觉好像确实是挺傻的。。对于一棵树建一个主席树。。每一个节点记录他到根的信息。。然后查询x，y两点之间的链的信息就只要x+y-lca(x,y)-fa[lca(x,y)]就好了。。。#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
const int M = 2000005;
struct data{int x,y,next;} e[N<<1];
int ls[M],rs[M],sum[M],num[N],v[N],hash[N],tmp[N],n,m,x,y,cnt,tot,head[N],ind,pos[N],deep[N],fa[N][20],sz,rt[N],rk,last;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(int x,int y){
e[++cnt].x = x;e[cnt].y = y;
e[cnt].next = head[x];head[x] = cnt;
}
int find(int x){
int l = 1,r = tot;
while (l<=r){
int mid = (l+r)>>1;
if (hash[mid]>x) r = mid-1;
else if (hash[mid]<x) l = mid+1;
else if (hash[mid]==x) return mid;
}
}
void dfs(int x){
num[++ind] = x;pos[x] = ind;
for (int i=1;i<=16;i++)
if ((1<<i)<=deep[x]) fa[x][i] = fa[fa[x][i-1]][i-1];
else break;
for (int i=head[x];i;i=e[i].next)
if (e[i].y!=fa[x][0]){
deep[e[i].y] = deep[x]+1;
fa[e[i].y][0] = x;
dfs(e[i].y);
}
}
int lca(int x,int y){
if (deep[x]<deep[y]) swap(x,y);
int d = deep[x]-deep[y];
for (int i=0;i<=16;i++)
if (d&(1<<i)) x = fa[x][i];
for (int i=16;i>=0;i--)
if (fa[x][i]!=fa[y][i]) x = fa[x][i],y = fa[y][i];
if (x==y) return x;
else return fa[x][0];
}
void Update(int l,int r,int x,int &y,int num){
y = ++sz;
sum[y] = sum[x]+1;
if (l==r) return;
ls[y] = ls[x];rs[y] = rs[x];
int mid = (l+r)>>1;
if (num<=mid) Update(l,mid,ls[x],ls[y],num);
else Update(mid+1,r,rs[x],rs[y],num);
}
int Query(int x,int y,int rk){
int a = x,b = y,c = lca(x,y),d = fa[c][0];
a = rt[pos[a]],b = rt[pos[b]],c = rt[pos[c]],d = rt[pos[d]];
int l = 1,r = tot;
while (l<r){
int mid = (l+r)>>1;
int tmp = sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
if (tmp>=rk){r = mid;a = ls[a];b = ls[b];c = ls[c];d = ls[d];}
else {rk-=tmp;l = mid+1;a = rs[a];b = rs[b];c = rs[c];d = rs[d];}
}
return hash[l];
}
int main(){
n = read();m = read();
for (int i=1;i<=n;i++) tmp[i] = v[i] = read();
sort(tmp+1,tmp+1+n);
hash[++tot] = tmp[1];
for (int i=2;i<=n;i++)
if (tmp[i]!=tmp[i-1]) hash[++tot] = tmp[i];
for (int i=1;i<=n;i++) v[i] = find(v[i]);
for (int i=1;i<n;i++){
x = read();y = read();
Insert(x,y);Insert(y,x);
}
dfs(1);
for (int i=1;i<=n;i++){
int t = num[i];
Update(1,tot,rt[pos[fa[t][0]]],rt[i],v[t]);
}
for (int i=1;i<=m;i++){
x = read();y = read();rk = read();
x^=last;last = Query(x,y,rk);
printf("%d",last);
if (i!=m) printf("\n");
}
}
评论 (0)
