[COCI2017-2018#2] Usmjeri
题意翻译
给定一颗从1到n编号的n个结点的树
同时给定m个约束,诸如$(a_i,b_i)$
给每一条边定向,使得对于每一对约束对存在一条从$a_i$到$b_i$或从$b_i$到$a_i$的路径。
求可行的方案数,答案对$10^9 + 7$取模
$1 \le n,m \le 3 \times 10^5$
```
给定一颗从1到n编号的n个结点的树
同时给定m个约束,诸如$(a_i,b_i)$
给每一条边定向,使得每一对约束对存在一条从$a_i$到$b_i$或从$b_i$到$a_i$的路径。
求可行的方案数,答案对$10^9 + 7$取模
$1 \le n,m \le 3 \times 10^5$
```
题目描述
We are given a tree with N nodes denoted with different positive integers from 1 to N.
Additionally, you are given M node pairs from the tree in the form of ($a_1$
, $b_1$
), ($a_2$
, $b_2$
), …, ($a_M$
,
$b_M$
).
We need to direct each edge of the tree so that for each given node pair ($a_i$
, $b_i$
) there is a
path from $a_i$
to $b_i$ or from $b_i$
to $a_i$
. How many different ways are there to achieve this?
Since the solution can be quite large, determine it modulo $10^{9}+7$.
输入输出格式
输入格式
The first line of input contains the positive integers N and M (1 ≤ N, M ≤ $3*10^5$), the number of
nodes in the tree and the number of given node pairs, respectively.
Each of the following N - 1 lines contains two positive integers, the labels of the nodes
connected with an edge.
The $i_{th}$ of the following M lines contains two different positive integers $a_{i}$ and $b_{i}$
, the labels of
the nodes from the $i_{th}$ node pair. All node pairs will be mutually different.
输出格式
You must output a single line containing the total number of different ways to direct the
edges of the tree that meet the requirement from the task, modulo $10^{9}+7$.
输入输出样例
输入样例 #1
4 1
1 2
2 3
3 4
2 4
输出样例 #1
4
输入样例 #2
7 2
1 2
1 3
4 2
2 5
6 5
5 7
1 7
2 6
输出样例 #2
8
输入样例 #3
4 3
1 2
1 3
1 4
2 3
2 4
3 4
输出样例 #3
0
说明
In test cases worth 20% of total points, the given tree will be a chain. In other words, node i
will be connected with an edge to node i + 1 for all i < N.
In additional test cases worth 40% of total points, it will hold N, M ≤ $5*10^3$.
A tree is a graph that consists of N nodes and N - 1 edges such that there exists a path from each
node to each other node.