题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4776
参见大牛题解http://blog.csdn.net/dslovemz/article/details/15290899。
自己比赛的时候除了枚举每一位之外，就没什么想法了，看了大牛题解，思路才略为明朗。此题的关键还是在于K比较小,1 <= k <= 200000。
先预处理一下树，求出根节点到每个节点的异或值，用此建出来一棵01字典树。
求第k大之前，可以先想想如何去求第一大。把第一大求出来过后，就可以考虑如何放水，使得值变为第二大，再放水，得到第三大，以此下去。
先求出对于每个数来说，最大的异或值是多少,O(n*18)，顺便将经过的节点压栈，压栈是为了记录字典树上经过的路径，为了之后的回溯。回溯的过程就是求次大值的过程。
对于n个数来说，用一个优先队列来保存所有数当前与其他数xor的最大值，此时队列首元素就是所有n个数中两个数xor的最大值。
0.如果队列非空，每次将优先队列中的队首元素弹出，假设当前最大值是由u节点与v节点异或得到的。(u和v都是字典树上的两个叶子节点，表示两个数)。
1.如果u==v，那么continue，进行下一轮循环。
3.否则，当前队首元素中的最大值，即为第k大的数，此时k++。然后调整u能够得到的最大值，去求一个当前值的次大值，然后将次大值压入队列，继续0操作。
先看的题解，按照自己的思路构造了一下程序结构，开始敲代码去：
//start coding at 15:02 //debug from 16:15 #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <map> #include <cmath> #include <iostream> using namespace std; #define ForEdge(i,u) for(int i=head[u];i!=-1;i=edge[i].next) #define For(i,forN) for(int i=0;i<(forN);i++) #define Rep(forN,i) for(int i=(forN);i>=0;i--) #define _clr(x,y) memset(x,(y),sizeof(x)) #define mp make_pair #define sf scanf #define pf printf using namespace std; typedef __int64 LL; const int Maxn=110000,Maxl=61; struct Tire { int id[2*Maxn*Maxl+1][2],cnt[2*Maxn*Maxl+1],last[Maxn],curNode[Maxn],Ttot; int stk[Maxn][Maxl][2]; void init(){id[Ttot=0][0]=id[0][1]=0;} int createNode() { Ttot++; id[Ttot][0]=id[Ttot][1]=cnt[Ttot]=0; return Ttot; } void insert(LL tval) { LL curB=1ll<<60; int curId=0; For(i,Maxl) { int ind=(curB&tval)!=0; if(id[curId][ind]==0) id[curId][ind]=createNode(); curId=id[curId][ind]; curB>>=1; } cnt[curId]++; } LL getMax(LL tval,int u) { LL curB=1ll<<60,ans=0; int curId=0; For(i,Maxl) { int ind=((curB&tval)==0); if(id[curId][ind]==0) ind^=1; else ans|=curB; stk[u][i][0]=curId,stk[u][i][1]=ind;//将u所经过的路径压栈,第三维为0表示父节点，1表示是父节点的哪个孩子 curB>>=1; curId=id[curId][ind]; } if(ans==0 && cnt[curId]==1) return -1; last[u]=(ans==0?2:1); curNode[u]=curId; return ans; } LL getVal(LL tval,int u) { LL ans=0,curB=1ll<<60; For(i,Maxl) { int ind=(curB&tval)!=0; if(stk[u][i][1]^ind) ans|=curB; curB>>=1; } return ans; } LL getNextMax(LL tval,int u) { if(last[u]<cnt[curNode[u]]) {last[u]++;return getVal(tval,u);} int curDeep=60,curId; LL curB=1; while(curDeep>=0) { int ind=(curB&tval)==0; curId=stk[u][curDeep][0]; if(stk[u][curDeep][1]==ind && id[curId][ind^1]!=0) break; else curDeep--,curB<<=1; } if(curDeep<0) return -1; stk[u][curDeep][1]^=1; curId=id[curId][stk[u][curDeep][1]]; curB>>=1,curDeep++; while(curDeep<Maxl) { int ind=(curB&tval)==0; if(id[curId][ind]==0) ind^=1; stk[u][curDeep][0]=curId,stk[u][curDeep][1]=ind; curId=id[curId][ind],curB>>=1,curDeep++; } LL ans=getVal(tval,u); if(ans==0 && cnt[curId]==1) return -1; last[u]=(ans==0?2:1); curNode[u]=curId; if(ans==5 && u==3) { For(i,Maxl) cout<<stk[u][i][1]<<" ";cout<<endl; } return ans; } }tire; int head[Maxn],etot,n,K; struct Edge { int to,next; LL cost; }edge[Maxn*2]; void init_edge() { etot=0;_clr(head,-1); } void add_edge(int u,int v,LL cost) { edge[etot].cost=cost; edge[etot].to=v; edge[etot].next=head[u]; head[u]=etot++; } LL val[Maxn]; bool vis[Maxn]; void dfs(int u) { vis[u]=true; ForEdge(i,u) { int v=edge[i].to; if(!vis[v]) { val[v]=val[u]^edge[i].cost; dfs(v); } } } LL Ans[Maxn*2]; LL dAns[Maxn]; void debug() { for(int i=1;i<=n;i++) cout<<val[i]<<" ";cout<<endl; //for(int i=1;i<=n;i++) cout<<tire.getMax(val[i],i)<<" ";cout<<endl; int tcnt=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) continue; else dAns[tcnt++]=val[i]^val[j]; sort(dAns,tcnt+dAns); sort(Ans+1,Ans+K+1); for(int i=0;i<tcnt;i++)cout<<dAns[i]<<" ";cout<<endl; for(int i=1;i<=K;i++) cout<<Ans[i]<<" ";cout<<endl; } void solve() { _clr(vis,false); val[1]=0; dfs(1); tire.init(); for(int i=1;i<=n;i++) tire.insert(val[i]); priority_queue < pair < LL ,int > > q; for(int i=1;i<=n;i++) { LL tmp=tire.getMax(val[i],i); if(tmp>=0) q.push(mp(tmp,i)); } K=0; while(!q.empty() && K<Maxn*2) { int u=q.top().second; LL tmp=q.top().first; q.pop(); if(tmp<0) continue; Ans[++K]=tmp; tmp=tire.getNextMax(val[u],u); if(tmp!=-1) q.push(mp(tmp,u)); } } int main() { while(~sf("%d",&n) && n) { int u,v; LL cost; init_edge(); For(i,n-1) sf("%d%d%I64d",&u,&v,&cost),add_edge(u,v,cost),add_edge(v,u,cost); solve(); int m; sf("%d",&m); while(m--) { int k; sf("%d",&k); if(k<=0 || k>K) puts("-1"); else pf("%I64d ",Ans[k]); } } return 0; }