老题解批量补档。
给定一棵带权树，将 \((u,v)\) 间简单路径上的边权生成数组，两个人在数组中轮流选数，每次选走的数必须 \(\le\) 上一个人选走的数，不能选的人输，问有多少个 \((u,v)\) 满足先手必胜。
如果在 \((u, v)\) 的路径上有任何一种边权的数量是奇数，那么就要统计 \((u,v)\)。
对于最小的、出现次数为奇数的边权 \(w\)，先手选择 \(w\)，此时剩下偶数个可选项。后手选择 \(w'\)，这会删除 \(>w'\) 且 \(\le w\) 的所有可选项。发现被删掉偶数个选项；剩下奇数个选项。易知先手必胜。
若不存在出现次数为奇数的边权，从刚刚后手的处境可以看出先手必败。所以，问题就转化为了：统计点对 \((u, v)\) 的数量，满足 \(u\) 到 \(v\) 的简单路径中存在出现次数为奇数的边权。
给每个边权映射一个值，为 base 的 rand() 次方，自然溢出即可。然后直接按照之前的操作处理就好了。
如果一个你想找到类似于 1 ^ 2 ^ 3 = 0 的情况，其出现概率与数字的二进制位数有关。因为 xor 只针对于同一位，结果不会被上一位或下一位干扰，所以每一位出现异或起来为 \(0\) 的概率是 \(\dfrac 12\)。只要我们整点比较强力的 \(k\) 位二进制数，那么出现以上情况的概率就是 \(2^{-k}\)。
那么这个比较强力的 \(k\) 位二进制数，用比较强力的类字符串哈希生成方式，再使用一个很大很大的随机数替代字符串哈希中表示下标的 \(i\)，用自然溢出让它显得更加稳妥就好。所以现在我们程序寄掉的概率就是 \(\dfrac 1{2^{64}}\)，好事情啊好事情。
时间复杂度 \(\mathcal O(n\log n)\)，\(\log n\) 来源于映射。
namespace XSC062 {
using namespace fastIO;
const int _p = 13331;
const int maxn = 5e5 + 5;
struct _ {
int v;
ull w;
_ () {}
_ (int v1, ull w1) {
v = v1, w = w1;
}
};
ull w;
ull f[maxn];
int T, n, x, y, ans;
std::map<ull, int> t;
std::map<ull, ull> q;
std::vector<_> g[maxn];
inline void Init(int n) {
t.clear();
q.clear();
for (int i = 1; i <= n; ++i) {
f[i] = 0;
g[i].clear();
g[i].shrink_to_fit();
}
return;
}
void DFS(int x, int fa) {
++t[f[x]];
for (auto i : g[x]) {
if (i.v == fa)
continue;
f[i.v] = f[x] ^ i.w;
DFS(i.v, x);
}
return;
}
inline void add(int x, int y, ull w) {
g[x].push_back(_(y, w));
return;
}
inline ull randint(void) {
ull res = rand();
res *= rand();
res *= rand();
return res;
}
inline ull qkp(ull x, ull y) {
ull res = 1;
while (y) {
if (y & 1)
res *= x;
x *= x;
y >>= 1;
}
return res;
}
int main() {
read(T);
srand(time(NULL));
while (T--) {
read(n);
Init(n);
ans = n * (n - 1) / 2;
for (int i = 1; i < n; ++i) {
read(x), read(y), read(w);
if (!q.count(w))
q[w] = qkp(_p, randint());
w = q[w];
add(x, y, w), add(y, x, w);
}
DFS(1, -1);
for (auto i : t)
ans -= i.second * (i.second - 1) / 2;
print(ans, '\n');
}
return 0;
}
} // namespace XSC062