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 必胜的 的选值个数。