시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
11 초 (추가 시간 없음) | 512 MB | 73 | 42 | 35 | 61.404% |
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 root.
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 nodes in the subtree of u in the tree rooted at r as Tr(u).
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 there exist nodes u and v where S = Tr(u) ∩ Tp(v).
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.
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 numbered from 1 to n.
Each of the next n − 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ n, u ≠ v), indicating an undirected edge between nodes u and v. It is guaranteed that this set of edges forms a 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.
5 2 1 2 2 3 2 4 4 5 1 3 4 5
8 6
The possible rootings of the first tree are
Considering the rootings at 1 and 3, the 8 obtainable sets are:
If the rootings are instead at 4 and 5, there are only 6 obtainable sets:
For some of these, there are other ways to choose u and v to arrive at the same set.