3747: 博弈(第四轮01)
题目描述
crying 和 dino 喜欢玩♂游♂戏。
她们在一棵树上玩游戏，已知树有 n 个点，编号从 1 到 n。第 i 边有一个正 整数边权 wi 。
crying 和 dino 会在这棵树上玩很多次游戏。每次游戏开始前， 清楚姐姐都会 给定一个点对 (u, v)，（u, v 为树上不同两点）然后把树上 u 到 v 的路径上所 有边的边权拿出来，生成一个数组 S。
crying 和 dino 轮流在 S 上进行以最优策略进行游戏， crying 为先手。
游戏的具体规则是这样的：
1. crying 第一次取走一个数。
2. 记上一个人取走的数的值为 x ，当前的人需要从 S 中取走一个不大于 x 的 数。不能进行操作的人输。
清楚姐姐觉得这个游戏十分地有趣，她想知道，在所有可能的初始点对 (u, v) 中， 有多少种情况能使 crying 有必胜策略。
输入
本题采用捆绑测试，第一行一个正整数 T，表示数据组数。
对于每一组数据，描述一棵树。
第一行一个正整数 n，表示树的大小。
接下来 n − 1 行，每行三个数 u, v, w，代表树上有一条边权为 w 的，连接点 u，点 v 的边。
输出
对于每组数据，输出一行一个数，表示有多少种初始点对能使 crying 有必胜策 略。
样例输入 复制
3
5
1 2 2
1 3 1
3 4 1
3 5 2
5
1 2 0
2 3 2
3 4 2
4 5 0
5
1 2 0
1 3 1
3 4 0
3 5 2样例输出 复制
9
8
10提示
样例 1 输入】
3
5
1 2 2
1 3 1
3 4 1
3 5 2
5
1 2 0
2 3 2
3 4 2
4 5 0
5
1 2 0
1 3 1
3 4 0
3 5 2
【样例 1 输出】
9
8
10
【样例 1 说明】
对于第一组数据，树的形态如下：
可以发现， 一共有 (2(5)) = 10 种选点对的方案。
当选的点对为 (1,4) 时：
- S = {1,1}。
- crying 取 1， S = {1}。
- dino 取 1， S = {}。
- crying 无法继续操作， dino 获胜。
可以发现，选其他点对的时候 crying 均有必胜策略，故最终的答案为 10 − 1 = 9。
【数据范围】
对于 27% 的数据， n ≤ 5000。
对于 100% 的数据， 1 ≤ T ≤ 10,1 ≤ ∑n ≤ 5 × 10^5 ,1 ≤ u, v ≤ n ≤ 5 × 10^5 ,0 ≤ w ≤ 10^9 ，保证给定的图是一棵树。