可持久化线段树
maya……树么……转化成序列……所以就写了个树链剖分……然后每个点保存的是从它到根的可持久化线段树。
然后就像序列一样查询……注意是多个左端点和多个右端点，处理方法类似BZOJ 1901
然后rausen（Orz！！！）粗来跟我说：你直接减去lca和fa[lca]不就好啦~搞树剖还多一个log……
我恍然大悟！然后两个都交了一下，事实证明：我链剖写的还行，LCA写的太丑……速度反而是多一个log的链剖快QAQ（另：因为边少我就偷懒没写边表，直接vector水过）
链剖：
/**************************************************************
Problem: 2588
User: ProgrammingApe
Language: C++
Result: Accepted
Time:3768 ms
Memory:47652 kb
****************************************************************/ //BZOJ 2588
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>;
/*******************template********************/
struct tree{
int cnt,l,r;
}t[N*];
int root[N],cnt,num;
int lc,rc,ln[N],rn[N];
#define mid (l+r>>1)
void update(int &o,int l,int r,int pos){
t[++cnt]=t[o]; o=cnt; t[o].cnt++;
if (l==r) return;
if (pos<=mid) update(t[o].l,l,mid,pos);
else update(t[o].r,mid+,r,pos);
}
int query_t(int rank){
int l=,r=num;
int tl=,tr=;
while(l!=r){
tl=tr=;
F(i,,lc) tl+=t[t[ln[i]].l].cnt;
F(i,,rc) tr+=t[t[rn[i]].l].cnt;
if (tr-tl>=rank){
F(i,,lc) ln[i]=t[ln[i]].l;
F(i,,rc) rn[i]=t[rn[i]].l;
r=mid;
}else{
F(i,,lc) ln[i]=t[ln[i]].r;
F(i,,rc) rn[i]=t[rn[i]].r;
l=mid+; rank-=tr-tl;
}
}
return l;
}
/*****************可持久化线段树 ***************/
vector<int>G[N];
int top[N],fa[N],son[N],dep[N],tot,size[N],a[N],b[N],n,m,lastans;
bool vis[N];
void dfs(int x,int f,int d){
vis[x]=;
fa[x]=f; dep[x]=d; size[x]=; son[x]=;
int maxsize=;
rep(i,G[x].size()){
int to=G[x][i];
if (vis[to]) continue;
dfs(to,x,d+);
size[x]+=size[to];
if (size[to]>maxsize) maxsize=size[to],son[x]=to;
}
}
void connect(int x,int f){
vis[x]=;
root[x]=root[fa[x]];
update(root[x],,num,a[x]);
// root[x]=++tot;
top[x]=f;
if (son[x]) connect(son[x],f);
rep(i,G[x].size()){
int to=G[x][i];
if (!vis[to]) connect(to,to);
}
}
void query(int x,int y,int k){
lc=rc=;
while(top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ln[++lc]=root[fa[top[x]]]; rn[++rc]=root[x];
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ln[++lc]=root[fa[x]]; rn[++rc]=root[y];
printf("%d",lastans=b[query_t(k)]);
}
/**********************链剖*********************/
int main(){
// freopen("input.txt","r",stdin);
n=getint(); m=getint();
F(i,,n) b[i]=a[i]=getint();
sort(b+,b+n+);
num=unique(b+,b+n+)-b-;
F(i,,n) a[i]=lower_bound(b+,b+num+,a[i])-b; int x,y,k;
F(i,,n){
x=getint(); y=getint();
G[x].pb(y); G[y].pb(x);
}
dfs(,,);
memset(vis,,sizeof vis);
connect(,); F(i,,m){
x=lastans^getint(); y=getint(); k=getint();
query(x,y,k);
if (i!=m) puts("");
}
return ;
}
倍增LCA：
/**************************************************************
Problem: 2588
User: Tunix
Language: C++
Result: Accepted
Time:4520 ms
Memory:53024 kb
****************************************************************/ //BZOJ 2588
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>;
/*******************template********************/
struct tree{
int cnt,l,r;
}t[N*];
int root[N],cnt,num;
int lc,rc,ln[N],rn[N];
#define mid (l+r>>1)
void update(int &o,int l,int r,int pos){
t[++cnt]=t[o]; o=cnt; t[o].cnt++;
if (l==r) return;
if (pos<=mid) update(t[o].l,l,mid,pos);
else update(t[o].r,mid+,r,pos);
}
int query_t(int rank){
int l=,r=num;
int tl=,tr=;
while(l!=r){
tl=tr=;
F(i,,lc) tl+=t[t[ln[i]].l].cnt;
F(i,,rc) tr+=t[t[rn[i]].l].cnt;
if (tr-tl>=rank){
F(i,,lc) ln[i]=t[ln[i]].l;
F(i,,rc) rn[i]=t[rn[i]].l;
r=mid;
}else{
F(i,,lc) ln[i]=t[ln[i]].r;
F(i,,rc) rn[i]=t[rn[i]].r;
l=mid+; rank-=tr-tl;
}
}
return l;
}
/*****************可持久化线段树 ***************/
vector<int>G[N];
int fa[N][],dep[N],a[N],b[N],n,m,lastans;
void dfs(int x){
F(i,,)
if (dep[x]>=(<<i)) fa[x][i]=fa[fa[x][i-]][i-];
else break;
root[x]=root[fa[x][]];
update(root[x],,num,a[x]);
rep(i,G[x].size()){
int to=G[x][i];
if (to==fa[x][]) continue;
fa[to][]=x; dep[to]=dep[x]+;
dfs(to);
}
}
int LCA(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
for(int i=;(<<i)<=t;i++)
if(t&(<<i)) x=fa[x][i];
D(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 query(int x,int y,int k){
lc=rc=;
int lca=LCA(x,y);
ln[++lc]=root[lca]; ln[++lc]=root[fa[lca][]];
rn[++rc]=root[x]; rn[++rc]=root[y];
printf("%d",lastans=b[query_t(k)]);
}
/**********************LCA*********************/
int main(){
n=getint(); m=getint();
F(i,,n) b[i]=a[i]=getint();
sort(b+,b+n+);
num=unique(b+,b+n+)-b-;
F(i,,n) a[i]=lower_bound(b+,b+num+,a[i])-b; int x,y,k;
F(i,,n){
x=getint(); y=getint();
G[x].pb(y); G[y].pb(x);
}
dfs(); F(i,,m){
x=lastans^getint(); y=getint(); k=getint();
query(x,y,k);
if (i!=m) puts("");
}
return ;
}
2588: Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit: 128 MB
Submit: 2581 Solved: 586
[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
暴力自重。。。