#P18088. XOR and LCA
XOR and LCA
XOR and LCA
题目描述
给定一棵有 个结点的树,结点编号为 。
记 为把整棵树以结点 为根时,结点 的最近公共祖先。求
$$\bigoplus_{0\le u<v<2^n}\operatorname{lca}_{u\oplus v}(u,v),$$其中 和外层 都表示按位异或。不同点对使用的根可以不同。
输入格式
第一行一个整数 ,表示测试组数。每组第一行一个整数 ;接下来 行,每行两个整数 ,表示一条无向边。
,,,。保证每组边构成一棵树;所有组的 之和不超过 。
输出格式
每组输出一行一个整数,表示所求的异或和。
样例输入
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