codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1843D.md (3522B)


      1 Source: https://codeforces.com/problemset/problem/1843/D
      2 
      3 D. Apple Tree
      4 
      5 time limit per test
      6 
      7 4 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Timofey has an apple tree growing in his garden; it is a rooted tree of $n$ vertices with the root in vertex $1$ (the vertices are numbered from $1$ to $n$). A tree is a connected graph without loops and multiple edges.
     22 
     23 This tree is very unusual — it grows with its root upwards. However, it's quite normal for programmer's trees.
     24 
     25 The apple tree is quite young, so only two apples will grow on it. Apples will grow in certain vertices (these vertices may be the same). After the apples grow, Timofey starts shaking the apple tree until the apples fall. Each time Timofey shakes the apple tree, the following happens to each of the apples:
     26 
     27 Let the apple now be at vertex $u$.
     28 
     29 * If a vertex $u$ has a child, the apple moves to it (if there are several such vertices, the apple can move to any of them).
     30 * Otherwise, the apple falls from the tree.
     31 
     32 It can be shown that after a finite time, both apples will fall from the tree.
     33 
     34 Timofey has $q$ assumptions in which vertices apples can grow. He assumes that apples can grow in vertices $x$ and $y$, and wants to know the number of pairs of vertices ($a$, $b$) from which apples can fall from the tree, where $a$ — the vertex from which an apple from vertex $x$ will fall, $b$ — the vertex from which an apple from vertex $y$ will fall. Help him do this.
     35 
     36 Input
     37 
     38 The first line contains integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     39 
     40 The first line of each test case contains integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the number of vertices in the tree.
     41 
     42 Then there are $n - 1$ lines describing the tree. In line $i$ there are two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) — edge in tree.
     43 
     44 The next line contains a single integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of Timofey's assumptions.
     45 
     46 Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i, y_i \leq n$) — the supposed vertices on which the apples will grow for the assumption $i$.
     47 
     48 It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$. Similarly, It is guaranteed that the sum of $q$ does not exceed $2 \cdot 10^5$.
     49 
     50 Output
     51 
     52 For each Timofey's assumption output the number of ordered pairs of vertices from which apples can fall from the tree if the assumption is true on a separate line.
     53 
     54 Examples
     55 
     56 Input
     57 
     58 ```
     59 2
     60 
     61 5
     62 
     63 1 2
     64 
     65 3 4
     66 
     67 5 3
     68 
     69 3 2
     70 
     71 4
     72 
     73 3 4
     74 
     75 5 1
     76 
     77 4 4
     78 
     79 1 3
     80 
     81 3
     82 
     83 1 2
     84 
     85 1 3
     86 
     87 3
     88 
     89 1 1
     90 
     91 2 3
     92 
     93 3 1
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 2
    100 2
    101 1
    102 4
    103 4
    104 1
    105 2
    106 ```
    107 
    108 Input
    109 
    110 ```
    111 2
    112 
    113 5
    114 
    115 5 1
    116 
    117 1 2
    118 
    119 2 3
    120 
    121 4 3
    122 
    123 2
    124 
    125 5 5
    126 
    127 5 1
    128 
    129 5
    130 
    131 3 2
    132 
    133 5 3
    134 
    135 2 1
    136 
    137 4 2
    138 
    139 3
    140 
    141 4 3
    142 
    143 2 1
    144 
    145 4 2
    146 ```
    147 
    148 Output
    149 
    150 ```
    151 1
    152 2
    153 1
    154 4
    155 2
    156 ```
    157 
    158 Note
    159 
    160 In the first example:
    161 
    162 * For the first assumption, there are two possible pairs of vertices from which apples can fall from the tree: $(4, 4), (5, 4)$.
    163 * For the second assumption there are also two pairs: $(5, 4), (5, 5)$.
    164 * For the third assumption there is only one pair: $(4, 4)$.
    165 * For the fourth assumption, there are $4$ pairs: $(4, 4), (4, 5), (5, 4), (5, 5)$.
    166 
    167  ![](https://espresso.codeforces.com/5514ad201e106b38b35b45b02e954944bd1e41f4.png) Tree from the first example. 
    168 
    169 For the second example, there are $4$ of possible pairs of vertices from which apples can fall: $(2, 3), (2, 2), (3, 2), (3, 3)$. For the second assumption, there is only one possible pair: $(2, 3)$. For the third assumption, there are two pairs: $(3, 2), (3, 3)$.