题号：NC221272
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
A tree is a connected, acyclic, undirected graph with n nodes and n − 1 edges. There is exactly
one path between any pair of nodes. A rooted tree is a tree with a particular node selected as the
Let T be a tree and Tr be that tree rooted at node r. The subtree of u in Tr is the set of all nodes
v where the path from r to v contains u (including u itself). In this problem, we denote the set of
You are given q queries. Each query consists of two (not necessarily different) nodes, r and p. A
set S is “obtainable” if and only if it can be expressed as the intersection of a subtree in the tree
rooted at r and a subtree in the tree rooted at p. Formally, a set S is “obtainable” if and only if
For a given pair of roots, count the number of different non-empty obtainable sets. Two sets are
different if and only if there is an element that appears in one, but not the other.
one path between any pair of nodes. A rooted tree is a tree with a particular node selected as the
root.
v where the path from r to v contains u (including u itself). In this problem, we denote the set of
nodes in the subtree of u in the tree rooted at r as Tr(u).
set S is “obtainable” if and only if it can be expressed as the intersection of a subtree in the tree
rooted at r and a subtree in the tree rooted at p. Formally, a set S is “obtainable” if and only if
there exist nodes u and v where S = Tr(u) ∩ Tp(v).
different if and only if there is an element that appears in one, but not the other.
输入描述:
The first line contains two space-separated integers n and q (1 ≤ n,q ≤ 2·105 ), where n is the
number of nodes in the tree and q is the number of queries to be answered. The nodes are numberedfrom 1 to n.Each of the next n − 1 lines contains two space-separated integers u and v (1 ≤ u,v ≤ n, uv),
indicating an undirected edge between nodes u and v. It is guaranteed that this set of edges formsa valid tree.Each of the next q lines contains two space-separated integers r and p (1 ≤ r,p ≤ n), which are
the nodes of the roots for the given query.
输出描述:
For each query output a single integer, which is the number of distinct obtainable sets of nodes that
can be generated by the above procedure.
备注:
The possible rootings of the first tree areConsidering the rootings at 1 and 3, the 8 obtainable sets are:
1. {1} by choosing u = 1, v = 1,
2. {1,2,4,5} by choosing u = 1, v = 2,
3. {1,2,3,4,5} by choosing u = 1, v = 3,
4. {2,3,4,5} by choosing u = 2, v = 3,
5. {2,4,5} by choosing u = 2, v = 2,
6. {3} by choosing u = 3, v = 3,
7. {4,5} by choosing u = 2, v = 4,
8. and {5} by choosing u = 5, v = 5.
If the rootings are instead at 4 and 5, there are only 6 obtainable sets:
1. {1} by choosing u = 1, v = 1,
2. {1,2,3} by choosing u = 2, v = 4,
3. {1,2,3,4} by choosing u = 4, v = 4,
4. {1,2,3,4,5} by choosing u = 4, v = 5,
5. {3} by choosing u = 3, v = 2,
6. and {5} by choosing u = 5, v = 5.
For some of these, there are other ways to choose u and v to arrive at the same set.
