| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 5 | 4 | 3 | 75.000% |
You are the proud owner of a newly built house in the Efficient Residences complex, so effectively built that there are no redundant streets in it, looking like a tree from higher up. Rumor has it that the constructor will start connecting houses to the sewage network. You know in which order will the constructor go through the houses. Since you want yours connected as soon as possible, you count up a bribe to change a small part of the ordering process in your favour.
You are given a tree with $N$ nodes that is rooted in the node with index $1$. You are also given the index of a node $K$, $1 \leq K \leq N$. We can do the following types of tree searches:
After we change the search type (e.g. in node $z$), we will only visit the nodes from $z$'s subtree further on. We suppose that $z$ was already visited in the first search.
You must compute for each of the two types of hybrid searches what is the smallest position in which the node with index $K$ can appear.
The tree neighbours are considered in the Breadth/Depth-First Searches in the order given in the input. You can consult below the exact implementations we use for DFS and BFS:
Algorithm 1 Depth-First Search (DFS) / Breadth-First Search (BFS)
function traversal(adj_lists, type):
p ← empty list {will contain the traversal nodes}
waiting ← empty list {behaves as either a stack or a queue, depending on type}
append (1, None) to waiting
while waiting is not empty:
(node, father) ← assign and pop rightmost if type = DFS else leftmost from waiting
append node to p
for each neigh in reversed(adj_lists[node]) if type = DFS else adj_lists[node]: {we need to reverse to enforce the input ordering for DFS}
if neigh ≠ father:
append (neigh, node) to waiting
traversal(adj_lists, type ← DFS or BFS)
The first line contains two numbers, $N$ and $K$ ($1 \leq N \leq 10^5$).
The next $N - 1$ lines contain two numbers each, $A$ and $B$ ($1 \leq A, B \leq N$). There is an edge in the tree between the nodes indexed $A$ and $B$.
If $Y$ and $Z$ are children of $X$ and the edge $X$ $Y$ (or $Y$ $X$) appears before the edge $X$ $Z$ (or $Z$ $X$) in the input, then $Y$ will appear before $Z$ in any DFS or BFS from a node whose subtree contains $X$.
Write on the first line the smallest position in the hybrid search the node indexed $K$ may be found (counting from $1$), if we start with a BFS.
Write on the second line the analog if we start with a DFS.
16 13 1 2 1 3 1 4 1 5 2 6 2 7 3 11 4 15 4 16 7 8 7 9 11 12 11 13 9 10 12 14
7 11
15 10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15
6 7
11 10 1 2 1 3 3 4 4 5 4 6 5 7 7 8 6 9 6 10 1 11
9 9
Figure H.1: For the first example, if we start with BFS, it is optimal to switch to DFS in node $3$, $K = 13$ being the seventh visited node. If we switched in node $11$ instead, we would have needed $11$ positions instead. If we start with DFS, we could optimally change in either node $3$ or node $11$.
Figure H.2: For the second example, if we start with DFS, it is also possible to achieve $7$ if we never change to BFS.
Figure H.3: For the third example, it doesn't matter with which search we begin, as both hybrid strategies have an optimal answer of $9$. Note that if we instead only used one of the two basic searches, we would have gotten both times an answer of $10$.