2588: Spoj 10628. Count on a tree
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
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)，表示一组询问。
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
Sample Output
2
8
9
105
7
HINT
HINT：
N,M<=100000
暴力自重。。。
题意
题解：
树上跑主席树
这类题都是这样搞……
代码来自hzwer:
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 2000005
#define eps 1e-9
int Num;
//const int inf=0x7fffffff; //§ß§é§à§é¨f§3
const int inf=0x3f3f3f3f;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//**************************************************************************************
#define N 100005
#define M 2000005
int n,m,tot,sz,cnt,ind,last;
int num[N],pos[N];
int v[N],tmp[N],hash[N],root[N];
int ls[M],rs[M],sum[M];
int deep[N],fa[N][];
struct data{int to,next;}e[];int head[N];
void ins(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v)
{ins(u,v);ins(v,u);}
int find(int x)//二分
{
int l=,r=tot;
while(l<=r)
{
int mid=(l+r)>>;
if(hash[mid]<x)l=mid+;
else if(hash[mid]==x)return mid;
else r=mid-;
}
}
void dfs(int x)//lca预处理
{
ind++;num[ind]=x;pos[x]=ind;
for(int i=;i<=;i++)
if((<<i)<=deep[x])fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int i=head[x];i;i=e[i].next)
if(fa[x][]!=e[i].to)
{
deep[e[i].to]=deep[x]+;
fa[e[i].to][]=x;
dfs(e[i].to);
}
}
int lca(int x,int y)//lca
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=;i<=;i++)
if((<<i)&t)x=fa[x][i];
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y)return x;
return fa[x][];
}
void update(int l,int r,int x,int &y,int num)//更新
{
y=++sz;
sum[y]=sum[x]+;
if(l==r)return;
ls[y]=ls[x];rs[y]=rs[x];
int mid=(l+r)>>;
if(num<=mid)
update(l,mid,ls[x],ls[y],num);
else update(mid+,r,rs[x],rs[y],num);
}
int que(int x,int y,int rk)
{
int a=x,b=y,c=lca(x,y),d=fa[c][];
a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];
int l=,r=tot;
while(l<r)
{
int mid=(l+r)>>;
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+,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
}
return hash[l];
}
int main()
{
//freopen("test.txt","r",stdin);
n=read(),m=read();
for(int i=;i<=n;i++)
v[i]=read(),tmp[i]=v[i];
sort(tmp+,tmp+n+);
hash[++tot]=tmp[];
for(int i=;i<=n;i++)
if(tmp[i]!=tmp[i-])hash[++tot]=tmp[i];
for(int i=;i<=n;i++)v[i]=find(v[i]);
for(int i=;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
}
dfs();
for(int i=;i<=n;i++)
{
int t=num[i];
update(,tot,root[pos[fa[t][]]],root[i],v[t]);
}
for(int i=;i<=m;i++)
{
int x=read(),y=read(),rk=read();
x^=last;
last=que(x,y,rk);
printf("%d",last);
if(i!=m)printf("\n");
}
return ;
}