579. 树上定向

单点时限: 6.0 sec

内存限制: 1024 MB

QQ小方以前不会做”唐纳德先生与网络降级计划“,现在他会了,所以他急切的想教会你。

选一个根,使得若干祖先和孩子的关系成立。

考虑任选一个为根,然后那些关系就是若干树上的路径。考虑

  • 如果 的祖先,说明根应该在 的子树外面。
  • 否则,根应该在 的子树里面。

题目保证有解,我们只要把解的范围缩小就可以了。对于「在子树外面」的那些约束,我们大可以无视,最后选答案的时候选一个深度最小的就可以了;而对于在子树里面的那些约束,就更好办了,维护一个最大的历史深度就好了。实现的时候可以合二为一,直接维护答案。

(这明明是 ultmaster 写的 月题解嘛。)

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

QQ小方将题目升级了。简单来说,QQ小方会给你一棵包含 个节点的树,并且会给你 个无序对 ,你需要将这棵树中的 条边进行定向,即对于一条边 ,你需要决定这条边是由 指向 或者 指向 。在进行全部的定位以后,得到的这棵树需要满足对于所有的无序对至少存在一条可行路径,即要么 能到达 、要么 能到达 。而现在,QQ小方想知道可行的定位方案数量。可行的定位方案数量可能很大,你只需要输出对 取模以后的答案。

输入格式

第一行一个整数 (),表示数据组数。

对于每组数据,首先有一行两个整数 (, )。

接下来 行,第 行两个整数 (, ) 表示 之间有一条无向边。保证无序对 在同组数据中至多出现一次。

接下来 行,第 行两个整数 (, )。无序对 可能出现多次。

输入保证所有测试数据的 不超过

输出格式

对于每组数据,输出一个整数表示答案。

样例

Input
2
4 1
1 2
2 3
3 4
2 4
4 3
1 2
1 3
1 4
2 3
2 4
3 4
Output
4
0

4 人解决,11 人已尝试。

4 份提交通过,共有 24 份提交。

8.6 EMB 奖励。

创建: 1 年,5 月前.

修改: 4 月,4 周前.

最后提交: 4 月,3 周前.

来源: EOJ Monthly 2019.5

题目标签