9999003 - 树上博弈

对于一棵 个节点的树,节点编号从 到 。每条边有一个边权,值域范围为 。 Alice 与 Bob 在这个树上做游戏。 首先在树上选择两个节点 , ,再选择一个值域区间 。 记变量 ,接下来两人轮流操作,Alice 先手。 对于每轮操作,在 到 的路径上,找一条权值在 范围内的边标记删除,然后把 调整为这一 权值。 不能进行操作的一方为负。 现在有 组独立的询问,每组询问给定三个整数 , , 。 问有多少个可能的正整数 ,满足选择的节点为 , ,选择的值域区间为 的情况下,如果游 戏双方都采取最优策略,则 Bob 最终会获胜。 对于每组询问,输出满足上述条件的 的个数。

输入

第一行一个整数 ,表示树上的节点个数。 N ≤ 1 ∼ 3 12 4 ∼ 6 20 7 ∼ 8 65 K = 1 9 ∼ 12 65 13 ∼ 20 500 2 ≤ N ≤ 500 1 ≤ wi,j ≤ 10 6 wi,j ≤ K ≤ 2 × wi,j N 1 N [0, N) u v [l, r] x = r u v [l, x] x M U V R L U V [L, R] L N 接下来 行,每行有三个整数 , , ,表示树上的一条边。 接下来一行一个整数 ,表示询问组数。 接下来 行,每行有三个整数 , , ,表示一组询问。

输出

对于每组询问,输出一行,表示令 Bob 必胜的 的选值个数。

样例

输入

7
1 2 2
1 3 7
3 4 3
3 5 7
5 6 6
5 7 7
9
6 4 5
3 6 7
5 4 1
6 1 6
3 6 3
5 1 2
4 2 4
2 7 7
1 1 1

输出

2
0
1
0
3
2
1
0
1
时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题