#P18088. XOR and LCA

XOR and LCA

XOR and LCA

题目描述

给定一棵有 2n2^n 个结点的树,结点编号为 0,1,…,2n−10,1,\ldots,2^n-1。

记 lca⁡r(u,v)\operatorname{lca}_r(u,v) 为把整棵树以结点 rr 为根时,结点 u,vu,v 的最近公共祖先。求

$$\bigoplus_{0\le u<v<2^n}\operatorname{lca}_{u\oplus v}(u,v),$$

其中 ⊕\oplus 和外层 ⨁\bigoplus 都表示按位异或。不同点对使用的根可以不同。

输入格式

第一行一个整数 tt,表示测试组数。每组第一行一个整数 nn;接下来 2n−12^n-1 行,每行两个整数 ui,viu_i,v_i,表示一条无向边。

1≤t≤1041\le t\le10^4,1≤n≤211\le n\le21,0≤ui,vi<2n0\le u_i,v_i<2^n,ui≠viu_i\ne v_i。保证每组边构成一棵树;所有组的 2n2^n 之和不超过 2212^{21}。

输出格式

每组输出一行一个整数,表示所求的异或和。

样例输入

4
1
0 1
2
0 1
1 2
2 3
3
0 1
0 2
0 3
0 4
0 5
0 6
0 7
3
4 5
2 6
3 7
0 2
1 5
2 7
6 4

样例输出

1
2
0
4