2588: Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit: 128 MB[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
dfs序，然后求LCA；
分成两条链求第K小；
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cmath> #include<string> #include<queue> #include<algorithm> #include<stack> #include<cstring> #include<vector> #include<list> #include<set> #include<map> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-14 #define bug(x) cout<<"bug"<<x<<endl; const int N=1e5+30010,M=1e6+10,inf=2147483647; const ll INF=1e18+10,mod=2147493647; struct Chairmantree { int rt[N*20],ls[N*20],rs[N*20],sum[N*20]; int tot; void init() { tot=0; } void build(int l,int r,int &pos) { pos=++tot; sum[pos]=0; if(l==r)return; int mid=(l+r)>>1; build(l,mid,ls[pos]); build(mid+1,r,rs[pos]); } void update(int p,int c,int pre,int l,int r,int &pos) { pos=++tot; ls[pos]=ls[pre]; rs[pos]=rs[pre]; sum[pos]=sum[pre]+c; if(l==r)return; int mid=(l+r)>>1; if(p<=mid) update(p,c,ls[pre],l,mid,ls[pos]); else update(p,c,rs[pre],mid+1,r,rs[pos]); } int rank(int s,int e,int L,int R,int l,int r) { if(L<=l&&r<=R)return sum[e]-sum[s]; int mid=(l+r)>>1; int ans=0; if(L<=mid) ans+=rank(ls[s],ls[e],L,R,l,mid); if(R>mid) ans+=rank(rs[s],rs[e],L,R,mid+1,r); return ans; } int query(int L,int R,int S,int T,int l,int r,int k) { if(l==r)return l; int mid=(l+r)>>1; int x=sum[ls[R]]-sum[ls[L]]+sum[ls[T]]-sum[ls[S]]; if(k<=x) return query(ls[L],ls[R],ls[S],ls[T],l,mid,k); else return query(rs[L],rs[R],rs[S],rs[T],mid+1,r,k-x); } }; Chairmantree tree; struct edge { int v,next; }edge[N<<1]; int head[N],fa[N][30],edg,deep[N]; int in[N],out[N],tot,flag[N]; void init() { memset(in,0,sizeof(in)); memset(deep,0,sizeof(deep)); memset(head,-1,sizeof(head)); edg=0; tot=0; } void add(int u,int v) { edg++; edge[edg].v=v; edge[edg].next=head[u]; head[u]=edg; } void dfs(int u,int fat) { tot++; in[u]=tot; for (int i=1; i<=18 ;i++) { if(deep[u]<(1<<i)) break; fa[u][i] = fa[fa[u][i-1]][i-1]; } for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fat) continue; deep[v]=deep[u]+1; fa[v][0]=u; dfs(v,u); } out[u]=tot; } int RMQ_LCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); int d=deep[x]-deep[y]; for (int i=0; i<=18 ;i++) if((1<<i)&d) x=fa[x][i]; for (int i=18; 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]; } int a[N],b[N]; int getpos(int x,int n) { int p=lower_bound(b+1,b+1+n,x)-b; return p; } int main() { int n,m; int le=1e5+10; while(~scanf("%d%d",&n,&m)) { init(); tree.init(); tree.build(1,le,tree.rt[0]); for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1,0); for(int i=1;i<=n;i++) flag[in[i]]=i; for(int i=1;i<=n;i++) { int p=getpos(a[flag[i]],n); //cout<<p<<" "<<in[fa[flag[i]][0]]<<endl; tree.update(p,1,tree.rt[in[fa[flag[i]][0]]],1,le,tree.rt[i]); } int ans=0; while(m--) { int u,v,k; scanf("%d%d%d",&u,&v,&k); u^=ans; int w=RMQ_LCA(u,v); ans=b[tree.query(tree.rt[in[w]],tree.rt[in[v]],tree.rt[in[fa[w][0]]],tree.rt[in[u]],1,le,k)]; printf("%d",ans); if(m) printf(" "); } } return 0; }