题目链接：

题意：

给你一棵有n个节点的树，每条边有一个权值a_i，现在定义两点直接的距离为路径上经过的边的异或和。

现在有m个询问，每次询问你第k长的路径是多少。

题解：

一开始我想二分+树分治+trie，发现只能做一个询问。- -!。

这里有一个优秀的做法，可以预处理出前k个答案。

首先，这里两点间的距离就是val[i]^val[j]，val[i]表示根节点到i节点的异或和。

然后我们可以将所有的val插进trie，然后我们将每个节点都作为起点，将以该起点的最大路径放进优先队列。

显然当前第一大的肯定就是优先队列的top，然后我们将这个top 记录下来，并且pop掉。

然后将产生这个top的节点x得到以x为起点的第二大路径放进优先队列。并且重复操作。

这样就可以将前k个答案以60*n*logn的复杂度预处理出来，然后询问就可以O(1)了。

1 #include
      
        2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 #define mst(a,b) memset(a,b,sizeof(a)) 4 using namespace std; 5 typedef long long ll; 6  7 const int N=2e5+7; 8 int n,m,g[N],v[N*2],nxt[N*2],ed; 9 ll w[N*2],val[N],z,ans[N];10 int ct,x,y,cnt[N*62],tr[N*62][2],tot;11 struct Node12 {13     int idx,k;14     ll val;15     Node(int a=0,int b=0,ll c=0):idx(a),k(b),val(c){}16     bool operator<(const Node &B)const{
    return val
       
        Q;19 20 void adg(int x,int y,ll z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}21 22 void dfs(int x,ll va,int fa)23 {24     val[x]=va;25     for(int i=g[x];i;i=nxt[i])26         if(v[i]!=fa)dfs(v[i],va^w[i],x);27 }28 29 void ins(ll a,int x=1)30 {31     for(int i=60;i>=0;i--)32     {33         int w=(a>>i)&1;34         if(!tr[x][w])35         {36             cnt[++tot]=0,mst(tr[tot],0);37             tr[x][w]=tot;38         }39         x=tr[x][w],cnt[x]++;40     }41 }42 43 ll kth(ll a,int k,int x=1,int i=60)44 {45     if(i<0)return 0;46     int w=(a>>i)&1;47     if(tr[x][w^1]&&cnt[tr[x][w^1]]>=k)48         return (1ll*(w^1)<
        
         n)continue;76             ll tp=kth(val[now.idx],now.k+1)^val[now.idx];77             Q.push(Node(now.idx,now.k+1,tp));78         }79         scanf("%d",&m);80         F(i,1,m)81         {82             scanf("%d",&x);83             printf("%lld\n",(x>ct||n==1)?-1:ans[x]);84         }85     }86     return 0;87 }