题目大意：
给定一棵n个点的树，每个点有一个权值，m个询问，每次询问树上点x到点y的路径上的第k小数。
思路：
dfs后给每个节点一个dfs序，以每个点在他父亲的基础上建立主席树，询问时用(点x+点y-点lca(x,y)-点dad[lca(x,y)])即可得到x到y的链，在上面查询即可。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define N 200009 5 using namespace std; 6 7 int tot=1,dfn,num,cnt,pa[N][18],to[N],next[N],head[N],lc[N*10],rc[N*10],deep[N],sum[N*10],id[N],pos[N],root[N],a[N],b[N]; 8 9 int read() 10 { 11 int x=0,y=1;char ch=getchar(); 12 while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();} 13 while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();} 14 return x*y; 15 } 16 17 void add(int x,int y) 18 { 19 to[++cnt]=y,next[cnt]=head[x],head[x]=cnt; 20 } 21 22 void dfs(int x) 23 { 24 int i;id[x]=++dfn,pos[dfn]=x; 25 for (i=1;i<=16;i++) 26 if ((1<<i)<=deep[x]) pa[x][i]=pa[pa[x][i-1]][i-1]; 27 else break; 28 for (i=head[x];i;i=next[i]) 29 if (pa[x][0]!=to[i]) 30 { 31 deep[to[i]]=deep[x]+1; 32 pa[to[i]][0]=x; 33 dfs(to[i]); 34 } 35 } 36 37 void change(int l,int r,int x,int &cur,int _cur) 38 { 39 cur=++num; 40 lc[cur]=lc[_cur]; 41 rc[cur]=rc[_cur]; 42 sum[cur]=sum[_cur]+1; 43 if (l==r) return; 44 int mid=l+r>>1; 45 if (x<=b[mid]) change(l,mid,x,lc[cur],lc[_cur]); 46 else change(mid+1,r,x,rc[cur],rc[_cur]); 47 } 48 49 int LCA(int x,int y) 50 { 51 if (deep[x]<deep[y]) swap(x,y); 52 int i,t=deep[x]-deep[y]; 53 for (i=0;i<=16;i++) 54 if ((1<<i)&t) x=pa[x][i]; 55 for (i=16;i>=0;i--) 56 if (pa[x][i]!=pa[y][i]) x=pa[x][i],y=pa[y][i]; 57 if (x==y) return x; 58 return pa[x][0]; 59 } 60 61 int ask(int x,int y,int k) 62 { 63 int a=root[id[x]],b=root[id[y]],c=LCA(x,y),d=pa[c][0],l=1,r=tot; 64 c=root[id[c]],d=root[id[d]]; 65 while (l<r) 66 { 67 int t=sum[lc[a]]+sum[lc[b]]-sum[lc[c]]-sum[lc[d]],mid=l+r>>1; 68 if (t>=k) a=lc[a],b=lc[b],c=lc[c],d=lc[d],r=mid; 69 else a=rc[a],b=rc[b],c=rc[c],d=rc[d],l=mid+1,k-=t; 70 } 71 return l; 72 } 73 74 int main() 75 { 76 int n=read(),m=read(),i,x,y,ans=0,k; 77 for (i=1;i<=n;i++) a[i]=read(),b[i]=a[i]; 78 for (i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x); 79 dfs(1),sort(b+1,b+n+1); 80 for (i=2;i<=n;i++) 81 if (b[tot]!=b[i]) b[++tot]=b[i]; 82 for(i=1;i<=n;i++) change(1,tot,a[pos[i]],root[i],root[id[pa[pos[i]][0]]]); 83 for (i=1;i<=m;i++) 84 { 85 x=read(),y=read(),k=read(),x^=ans; 86 printf("%d",ans=b[ask(x,y,k)]); 87 if (i<m) printf("\n"); 88 } 89 return 0; 90 }
转载于:https://www.cnblogs.com/HHshy/p/5823349.html
相关资源：JAVA上百实例源码以及开源项目