UVA13277 Xor Path

你有一颗有 $N$ 个结点的带边权无根树，结点从 $1$ 开始编号，边权是范围在 $\left [ 0,2^{16}-1 \right ]$ 以内的**整数**。对于树上的两点 $u,v$，定义 $\operatorname{d}(u,v)$ 为 $u$ 到 $v$ 路径上的边权的异或值。对于**每个** $x \in \left [ 0,2^{16}-1 \right ]$，求出使得 $\operatorname{d}(u,v)=x$ 的路径有多少条。 译者注：虽然本题没有明说，但据测试此处要求统计的二元组 $(u,v)$ 是无序的，且自己到自己的路径 $(u,u)$ 不算进答案内。

第一行是测试数据的组数 $T(T \le 10)$。 每一组数据有 $N$ 行，第一行是一个整数 $N(N\le 10^5)$。 接下来 $N-1$ 行，每行三个数字 $u,v,w$，表示结点 $u$ 和结点 $v$ 之间有条边权为 $w$ 的边。保证 $1\le u,v \le N$，$ w \in \left [ 0,2^{16}-1 \right ]$ 且 $w$ 是整数。

对于每一组测试数据请输出 $2^{16}+1$ 行。第一行输出一行字符串 `Case %d:`。其中 `%d` 表示该组数据是第几组。 接下来 $2^{16}$ 行，每一行输出一个整数表示对应的答案。 你**不需要**在两组数据之间输出**空行**将其隔开。 **请注意，题面给出的样例里省略了 $2^{16}-9$ 行 `0`。**

请注意，你可能需要使用 `long long` 类型的整型变量。