codeforces-scrape

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

1763.md (22295B)


      1 Source: https://codeforces.com/blog/entry/110278
      2 
      3 We hope you liked the problems! Unfortunately, problem C turned out to be harder than usual. Please read its editorial, we hope you'll find that the intended solution is not that hard.
      4 
      5 # [1763A - Absolute Maximization](/contest/1763/problem/A "Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT")
      6 
      7 Idea: [DreadArceus](/profile/DreadArceus "Specialist DreadArceus")  
      8  Prepared by: [DreadArceus](/profile/DreadArceus "Specialist DreadArceus")
      9 
     10 **Hint 1**
     11 
     12 Which $1$s in the binary representation cannot be changed to $0$.
     13 
     14 **Hint 2**
     15 
     16 Similarly, Which $0$s in the binary representation cannot be changed to $1$.
     17 
     18 **Need more hints?**
     19 
     20 Considering the last two hints, try to maximize the maximum element and minimize the minimum element.
     21 
     22 **Solution**
     23 
     24 In the minimum element, we want to make every bit $0$ when possible, it won't be possible to set a particular bit to $0$ when that bit is set in all the elements of $a$. Therefore, the minimum value we can achieve after performing the operations is the bitwise AND of all the elements of $a$.
     25 
     26 In the maximum element, we want to make every bit $1$ when possible, it won’t be possible to set a particular bit to $1$ when that bit is not set in any of the elements of $a$. Therefore, the maximum value we can achieve after performing the operations is the bitwise OR of all the elements of $a$.
     27 
     28 Therefore the answer is (OR of the array — AND of the array).
     29 
     30 Time Complexity: $O(n)$
     31 
     32 # [1763B - Incinerate](/contest/1763/problem/B "Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT")
     33 
     34 Idea: [og_](/profile/og_ "Pupil og_")  
     35  Prepared by: [og_](/profile/og_ "Pupil og_")
     36 
     37 **Hint 1**
     38 
     39 What if the array $p$ was sorted?
     40 
     41 **Hint 2**
     42 
     43 Is it necessary to decrease the health of each monster manually after every attack?
     44 
     45 **Solution 1**
     46 
     47 Sort the monsters in ascending order of their powers.
     48 
     49 Now we iterate through the monsters while maintaining the current attack power and the total damage dealt.
     50 
     51 Only the monsters with health greater than the total damage dealt are considered alive, and every time we encounter such a monster it will be the weakest one at the current time, thus we need to attack until the total damage dealt exceeds the current monster's health while lowering our attack power by its power each time.
     52 
     53 If we can kill all the monsters in this way, the answer is YES, otherwise it is NO.
     54 
     55 Time Complexity: $O(nlogn)$
     56 
     57 **Sort by power solution**
     58 
     59 [Code](https://pastebin.com/S2i8FM73) Author: [DreadArceus](/profile/DreadArceus "Specialist DreadArceus")
     60 
     61 **Solution 2**
     62 
     63 Sort the monsters in ascending order of their health.
     64 
     65 Now we maintain a count of monsters alive after each attack. This could be achieved by applying $upper bound()$ on $h$ array for each attack. The total damage dealt could be stored and updated in a separate variable.
     66 
     67 To find the power of the weakest monster alive, we could just precompute the minimum power of monsters in a suffix array. In other words,
     68 
     69 $p_i = \min(p_i, p_{i+1}).$
     70 
     71 Time Complexity: $O(nlogn)$
     72 
     73 **Sort by health solution**
     74 
     75 [Code](https://pastebin.com/Jv0K2K5k) Author: [og_](/profile/og_ "Pupil og_")
     76 
     77 # [1763C - Another Array Problem](/contest/1763/problem/C "Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT")
     78 
     79 Idea: [.utk.](/profile/.utk. "Specialist .utk.")  
     80  Prepared by: [.utk.](/profile/.utk. "Specialist .utk.")
     81 
     82 **Hint 1**
     83 
     84 What happens when we apply the same operation twice?
     85 
     86 **Hint 2**
     87 
     88 What about n = 3 ?
     89 
     90 **Solution**
     91 
     92 Let’s first consider the case for $n \geq 4$. The key observation to make here is that we can make all the elements of a subarray $a_l,...a_r$ zero by applying the operation on range $[l,r]$ twice. Then let’s assume the maximum element $mx$ of the array is at an index $m \gt r$. We can apply the operation on the range $[l,m]$ and turn all its elements into $mx$.
     93 
     94 Using the above information we can see that to achieve the final array with maximum sum we need to make all the elements in it equal to the maximum element in the array. Regardless of the given array this can be achieved by making the last two elements (n-1,n) zero. Then applying the operation on subarray $[m,n]$ to make all its elements equal to $mx$. Then making the first two elements (1,2) zero and applying the operation on the whole array making all the elements equal to $mx$. Thus the maximum sum for the final array will always be $n*mx$. (In case $m = n-1$ or $n$, we can operate on the left side first to reach the same solution).
     95 
     96 For $n = 2$ the maximum final sum would be $\max(a_1+a_2, 2*(|a_1-a_2|))$.
     97 
     98 For $n=3$, when the maximum element is present at index $1$ or $3$ we can make all the elements of the array into $mx$. When the maximum element is at index $2$, we have the following options.
     99 
    100 Case 1: We can apply the operation on (1,2), then we can convert all the elements of the array into $ \max(a_3,|a_2-a_1|)$.
    101 
    102 Case 2: We can apply the operation on (2,3), then we can convert all the elements of the array into $ \max(a_1,|a_2-a_3|)$.
    103 
    104 Case 3: We can apply the operation on (1,3) making all the elements in the array $|a_1-a_3|$. This is redundant since $a_2 \gt a_1,a_3$ either case 1 or case 2 will give a larger sum as $a_2 - \min(a_1,a_3) \gt \max(a_1,a_3) - \min(a_1,a_3)$.
    105 
    106 Now considering case 1, if $ 3* \max(a_3,|a_2-a_1|) \leq a_1+a_2+a_3 $ the maximum sum possible would be the current sum of the array (see sample 1 and 3). Therefore no operations are required. Similar case for case 2.
    107 
    108 So the maximum possible sum for $n=3$ will be $\max(3*a_1, 3*a_3, 3*|a_1-a_2|, 3*|a_3-a_2|,a_1+a_2+a_3)$.
    109 
    110 To avoid doing this casework for $n = 3$, we can see that there are only 3 possible operations -> (1,2) , (2,3), (1,3). We will be required to perform operations (1,2) and (2,3) at most two times. So we can brute force all possible combinations of operations [(1,2),(1,2),(2,3),(2,3),(1,3)] to find the maximum sum.
    111 
    112 **Brute force solution**
    113 
    114 [186019483](/contest/1763/submission/186019483 "Submission 186019483 by satyam343") Author: [satyam343](/profile/satyam343 "Candidate Master satyam343")
    115 
    116 **Case work solution**
    117 
    118 ```
    119 #include <bits/stdc++.h>
    120 using namespace std;
    121 #define int long long
    122 #define ll long long
    123 #define pii pair<ll, ll>
    124 int32_t mod = 1e9 + 7;
    125 
    126 void solve()
    127 {
    128     ll n;
    129     cin >> n;
    130     vector<ll> a(n);
    131     for (auto &i : a)
    132         cin >> i;
    133     if (n == 2)
    134         cout << max({2 * abs(a[0] - a[1]), a[0] + a[1]});
    135     else if (n == 3)
    136         cout << max({3 * (abs(a[0] - a[1])), 3 * (abs(a[2] - a[1])), 3 * a[0], 3 * a[2], a[0] + a[1] + a[2]});
    137     else
    138     {
    139         ll mx = 0;
    140         for (auto i : a)
    141             mx = max(i, mx);
    142         cout << n * mx;
    143     }
    144     cout<<'\n';
    145 }
    146 
    147 int32_t main()
    148 {
    149     ios::sync_with_stdio(false), cin.tie(NULL);
    150     ll t = 0;
    151     cin >> t;
    152     while (t--)
    153         solve();
    154 }
    155 ```
    156 
    157 Author: [.utk.](/profile/.utk. "Specialist .utk.")
    158 
    159 # [1763D - Valid Bitonic Permutations](/contest/1763/problem/D "Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT")
    160 
    161 Idea: [warks](/profile/warks "Expert warks")  
    162  Prepared by: [warks](/profile/warks "Expert warks")
    163 
    164 **Hint 1**
    165 
    166 Can you solve the problem when $x \lt y$?
    167 
    168 **Spoiler**
    169 
    170 When $x \gt y$, perform $i'=n-j+1$, $j'=n-i +1$, $x' = y$, and $y' = x$.
    171 
    172 **Hint 2**
    173 
    174 Can you solve the problem for a fixed value of $k$?
    175 
    176 **Spoiler**
    177 
    178 Iterate over possible values of $k$. The total count is the sum of the individual counts.
    179 
    180 **Hint 3**
    181 
    182 Club the remaining numbers into ranges as follows: $[1,x-1]$, $[x+1,y-1]$, and $[y+1,n-1]$.
    183 
    184 **Solution**
    185 
    186 For simplicity, if $x \gt y$, perform $i' = n-j+1$, $j' = n-i+1$, $x' = y$, and $y' = x$. Hereafter, the variables $i$, $j$, $x$, and $y$, will refer to these values. Now, $i \lt j$ and $x \lt y$.
    187 
    188 For now, assume that $y \lt n$. We shall consider the case where $y = n$ at a later stage.   
    189  Let us consider solving the problem for fixed $k$. Valid values for $k$ are $[2,i-1]$, $[i+1,j-1]$, $[j+1,n-1]$.   
    190  If we think about it, when $x \lt y$, $k$ cannot lie in the range $[2, i-1]$. So, we can discard them as possible values for $k$.
    191 
    192 Let us consider the case where $k$ belongs to $[i+1,j-1]$.   
    193  The permutation adheres to the following pattern: $B_1 \lt .. \lt B_i = x \lt .. \lt B_k = n \gt .. \gt B_j = y \gt .. \gt B_n$.
    194 
    195 * Numbers to the left of $i$ must lie in the range $[1,x-1]$. We choose $i-1$ elements from $[1,x-1]$ and place them to the left of $i$. There are ${x-1 \choose i-1}$ ways to do this. The remaining $x-i$ elements from $[1,x-1]$ lie to the right of $j$ by default.
    196 * Numbers to the right of $j$ must lie in the range $[1,x-1]$ or $[x+1,y-1]$. Since numbers in the range $[1,x-1]$ have already been placed, therefore, we choose numbers in the range $[x+1,y-1]$, and place them in the $n-j-(x-i)$ remaining positions. There are ${y-x-1 \choose n-j-(x-i)}$ ways to do this. The remaining elements in the range $[x+1,y-1]$ lie between $i$ and $k$ by default.
    197 * Numbers between $k$ and $j$ must lie in the range $[y+1,n-1]$. We choose $j-k-1$ elements from $[y+1,n-1]$ and place them between $k$ and $j$. There are ${n-y-1 \choose j-k-1}$ ways to do this. Afterwards, the remaining elements in the range lie between $i$ and $k$ by default, and the permutation is full.
    198 
    199 Multiplying the ways for the above three actions, we get that the answer for a fixed $k$, when between $i$ and $j$ as:   
    200  ${x-1 \choose i-1} * {y-x-1 \choose n-j-(x-i)} * {n-y-1 \choose j-k-1}$
    201 
    202 Let us consider the case where $k$ belongs to the range $[j+1,n-1]$.   
    203  The permutation adheres to the following pattern: $B_1 \lt .. \lt B_i = x \lt .. \lt B_j= y \lt .. \lt B_k = n \gt .. \gt B_n$.
    204 
    205 * Similar to above, the numbers to the left of $i$ must lie in the range $[1,x-1]$. We choose $i-1$ elements from $[1,x-1]$, and place them to the left of $i$. The remaining $x-i$ elements from $[1,x-1]$ lie to the right of $k$ by default.
    206 * Numbers between $i$ and $j$ must lie in the range $[x+1,y-1]$. We choose $j-i-1$ elements from $[x+1,y-1]$ and place them between $i$ and $j$. There are ${y-x-1 \choose j-i-1}$ ways to do this, and the remaining elements from $[x+1,y-1]$ lie to the right of $k$ by default.
    207 * Numbers between $j$ and $k$ must lie in the range $[y+1,n-1]$. We choose $k-j-1$ elements from $[y+1,n-1]$ and place them in these positions. Afterwards, the remaining elements in the range get placed to the right of $k$ by default, and the permutation is full.
    208 
    209 Multiplying the ways for the above three actions, we get the answer for a fixed $k$, when between $j+1$, and $n-1$ as: ${x-1 \choose i-1} * {y-x-1 \choose j-i-1} * {n-y-1 \choose k-j-1}$
    210 
    211 The answer to the problem is the sum of individual answers for all iterated values of $k$.
    212 
    213 $ans = {x-1 \choose i-1} * {y-x-1 \choose n-j-(x-i)} * \sum_{k=i+1}^{j-1} {n-y-1 \choose j-k-1}$ + ${x-1 \choose i-1} * {y-x-1 \choose j-i-1} * \sum_{k=j+1}^{n-1} {n-y-1 \choose k-j-1}$
    214 
    215 Let us now consider the case where $y = n$.   
    216  The permutation adheres to the following pattern: $B_1 \lt .. \lt B_i = x \lt .. \lt B_j = B_k = n \gt .. \gt B_n$.
    217 
    218 * Again, the numbers to the left of $i$ must lie in the range $[1,x-1]$. We choose $i-1$ elements from $[1,x-1]$ and place them to the left of $i$. The remaining $x-i$ elements from $[1,x-1]$ lie to the right of $j$ (here, $k$) by default.
    219 * Numbers between $i$ and $j$ must lie in the range $[x+1,y-1]$. We choose $j-i-1$ elements form $[x+1,y-1]$ and place them between $i$ and $j$. The remaining elements from $[x+1,y-1]$ lie to the right of $j$ (here, $k$) by default, and the permutation is full.
    220 
    221 Multiplying the ways for the above two actions, we get the answer for $k = j$ ($y = n$) as: ${x-1 \choose i-1} * {y-x-1 \choose j-i-1}$
    222 
    223 With $O(n_{max}*log(10^9+7-2))$ precomputation for factorials and their modular inverses, each individual test can be solved as above in $O(n)$. Therefore, the overall complexity of this approach is $O(n_{max}*log(10^9+7-2) + t*n)$, but the constraints allowed for slower solutions as well.
    224 
    225 $Bonus:$ Can you solve the problem when $1 \le t, n \le 10^5$.
    226 
    227 **Code**
    228 
    229 ```
    230 #include <iostream>
    231 #include <vector>
    232 using namespace std;
    233 
    234 const int MOD = 1000000007;
    235 vector<int> fac;
    236 vector<int> ifac;
    237 
    238 int binExp(int base, int exp) {
    239     base %= MOD;
    240     int res = 1;
    241     while (exp > 0) {
    242         if (exp & 1) {
    243             res = (int) ((long long) res * base % MOD);
    244         }
    245         base = (int) ((long long) base * base % MOD);
    246         exp >>= 1;
    247     }
    248     return res;
    249 }
    250 
    251 void precompute(int n) {
    252     fac.resize(n + 1);
    253     fac[0] = fac[1] = 1;
    254     for (int i = 2; i <= n; i++) {
    255         fac[i] = (int) ((long long) i * fac[i-1] % MOD);
    256     }
    257 
    258     ifac.resize(n + 1);
    259     for (int i = 0; i < fac.size(); i++) {
    260         ifac[i] = binExp(fac[i], MOD - 2);
    261     }
    262     return;
    263 }
    264 
    265 int nCr(int n, int r) {
    266     if ((n < 0) || (r < 0) || (r > n)) {
    267         return 0;
    268     }
    269     return (int) ((long long) fac[n] * ifac[r] % MOD * ifac[n - r] % MOD);
    270 }
    271 
    272 int countValidBitonicPerm(int n, int i, int j, int x, int y) {
    273     if (x > y) {
    274         i = n - i + 1;
    275         j = n - j + 1;
    276         swap(i, j);
    277         swap(x, y);
    278     }
    279 
    280     int sum = 0;
    281     for (int k = i + 1; k < j; k++) {
    282         sum += nCr(n - y - 1, j - k - 1);
    283         sum %= MOD;
    284     }
    285     int count = (int) ((long long) nCr (x - 1, i - 1) * nCr(y - x - 1, n - j - (x - i)) % MOD * sum % MOD);
    286 
    287     sum = 0;
    288     for (int k = j + 1; k < n; k++) {
    289         sum += nCr(n - y - 1, k - j - 1);
    290         sum %= MOD;
    291     }
    292     count += (int) ((long long) nCr(x - 1, i - 1) * nCr(y - x - 1, j - i - 1) % MOD * sum % MOD);
    293     count %= MOD;
    294 
    295     if (y == n) {
    296         if (j == n) {
    297             return 0;
    298         } else {
    299             return (int) ((long long) nCr(x - 1, i - 1) * nCr(y - x - 1, j - i - 1) % MOD);
    300         }
    301     }
    302     
    303     return count;
    304 }
    305 
    306 int main() {
    307     const int MAXN = 100;
    308     precompute(MAXN);
    309 
    310     int testCases;
    311     cin >> testCases;
    312     for (int test = 1; test <= testCases; test++) {
    313         int n, i, j, x, y;
    314         cin >> n >> i >> j >> x >> y;
    315         cout << countValidBitonicPerm(n, i, j, x, y) << endl;
    316     }
    317 
    318     return 0;
    319 }
    320 ```
    321 
    322 # [1763E - Node Pairs](/contest/1763/problem/E "Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT")
    323 
    324 Idea: [crimsonred](/profile/crimsonred "Expert crimsonred")  
    325  Prepared by: [...nvm](/profile/...nvm "Pupil ...nvm"), [DreadArceus](/profile/DreadArceus "Specialist DreadArceus"), [crimsonred](/profile/crimsonred "Expert crimsonred")
    326 
    327 **Hint 1**
    328 
    329 In a directed graph, which nodes are reachable from each other? How many such pairs of nodes exist?
    330 
    331 **Hint 2**
    332 
    333 Think about a sequence of SCCs.
    334 
    335 **Solution**
    336 
    337 For two nodes $u$ and $v$ to be reachable from each other, they must lie in the same strongly connected component (SCC). Let's define $f(i)$ as the minimum number of nodes required to construct an $i$-reachable graph. We can use dynamic programming and calculate $f(i)$ as $f(i) = \min(f(i — \frac{s (s — 1)}{2}) + s)$ over all the valid SCC sizes $s$ for which $\frac{s (s — 1)}{2} \leq i$, i.e., over those $s$ which have less pairs of the required type than $i$. Thus, $f(p)$ gives us the minimum number of nodes required to create a $p$-reachable graph.
    338 
    339 In all $p$-reachable graphs with $f(p)$ nodes, the upper bound on the number of unidirectional pairs of nodes is $\binom{f(p)}{2} - p$, because we have exactly $p$ pairs of nodes which are reachable from each other. It is possible to achieve this upper bound using the following construction: let $s_1, s_2, \ldots, s_k$ be any sequence of SCC sizes which agrees with the dp values we calculated earlier. Let the first SCC contain the nodes $[1, s_1]$, the second one contain $[s_1 + 1, s_1 + s_2]$, and so on. We add a directed edge from $u$ to $v$ if $u \lt v$.
    340 
    341 Time Complexity: $\mathcal{O}(p\sqrt{p})$
    342 
    343 **Code**
    344 
    345 ```
    346 #include <bits/stdc++.h>
    347 using namespace std;
    348 
    349 const int INF = 1e9;
    350 
    351 void solve()
    352 {
    353     int p;
    354     cin >> p;
    355  
    356     vector<int> dp(p + 1, INF);
    357     dp[0] = 0;
    358     for (int i = 1; i <= p; ++i)
    359         for (int s = 1; (s * (s - 1)) / 2 <= i; ++s)
    360             dp[i] = min(dp[i], dp[i - (s * (s - 1)) / 2] + s);
    361 
    362     cout << dp[p] << ' ' << ((long long) dp[p] * (dp[p] - 1)) / 2 - p << '\n';
    363 }
    364  
    365 int main()
    366 {
    367     solve();
    368     return 0;
    369 }
    370 ```
    371 
    372 # [1763F - Edge Queries](/contest/1763/problem/F "Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT")
    373 
    374 Idea: [...nvm](/profile/...nvm "Pupil ...nvm"), [DreadArceus](/profile/DreadArceus "Specialist DreadArceus")  
    375  Prepared by: [...nvm](/profile/...nvm "Pupil ...nvm"), [DreadArceus](/profile/DreadArceus "Specialist DreadArceus")
    376 
    377 **Hint 1**
    378 
    379 What kind of graph meets the conditions given in the statement?
    380 
    381 **Answer**
    382 
    383 A graph with bridges connecting components with a hamiltonian cycle.
    384 
    385 **Hint 2**
    386 
    387 Which edges will never be counted in answer to any query?
    388 
    389 **Answer**
    390 
    391 Of course, the bridges.
    392 
    393 **Hint 3**
    394 
    395 Restructure the graph to be able to answer queries.
    396 
    397 **Hint 4**
    398 
    399 $query(u, v)$ on a tree can be solved efficiently via Lowest Common Ancestor (LCA).
    400 
    401 **Solution**
    402 
    403 First, let us see examples of graphs that are valid or invalid according to the statement.
    404 
    405 **Valid Graph Example**
    406 
    407 ![](/predownloaded/bb/a0/bba0bdbb99fdacc0a38b208e125f05ee5e2be311.png)
    408 
    409 In this graph, for node $4$, the longest simple cycle is $4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$.
    410 
    411 $S_4 = {1, 2, 3, 4}$
    412 
    413 All simple cycles from node $4$ are $4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ and $4 \rightarrow 1 \rightarrow 3 \rightarrow 4$.
    414 
    415 $C_4 = {1, 2, 3, 4}$
    416 
    417 So, $S_4 = C_4$. Similarly, $S_u = C_u$ for all $u$.
    418 
    419 A tree of such components is also a valid graph!
    420 
    421 **Invalid Graph Example**
    422 
    423 ![](/predownloaded/34/d9/34d9fe7c92e7093e45269eb28bd483174e2193d9.png)
    424 
    425 Here, $S_4 = {1, 2, 3, 4}$ and $C_4 = {1, 2, 3, 4, 5, 6}$.
    426 
    427 So, $S_4 \neq C_4$
    428 
    429 The queries ask us to count all non-bridge edges in any simple path from $u$ to $v$.
    430 
    431 There are many ways to proceed with the solution. We will first go into a simple one that gives more insight into the problem.
    432 
    433 We can see our graph as a tree of BiConnected Components (BCCs).
    434 
    435 * The edges of the tree are all bridges.
    436 
    437 Let’s define a few things before continuing further.
    438 
    439 * The first node of a BCC that is visited in the DFS tree will represent that BCC.
    440 * Let $rep[u]$ be the representative of the BCC of node $u$.
    441 * $cnt[u]$ be the number of edges in the BCC of $u$.
    442 * Root node of our tree of BCCs is $root$.
    443 * $lca(u, v)$ is the lowest common ancestor of $u$ and $v$.
    444 
    445 With all that set, let us now look at the DFS tree.
    446 
    447 We can build an array $dp$ to store the answer to $query(root, u)$, for all $u$, and to answer queries, we can use LCA.
    448 
    449 In a typical LCA use case, query(u, v) would be $dp[u] + dp[v] - 2 * dp[lca(u, v)]$, But is that the case here?
    450 
    451 Let us bring attention to a few things.
    452 
    453 **First**
    454 
    455 Is $u = rep[u]$?
    456 
    457 **Why?**
    458 
    459 If $u = rep[u]$, $u$ is the first vertex of its BCC in the DFS tree. Therefore all the edges in the BCC of $u$ will not lie in any simple path from $u$ to $root$.
    460 
    461 Example:
    462 
    463 ![](/predownloaded/52/92/52927c2936929955620494463983681ff514023a.png)
    464 
    465 In this graph, Let's say $root$ is $1$.
    466 
    467 See that, $dp[3]$ should be $0$, and $dp[4]$ should be $3$. They are in the same BCC, but $3$ is the topmost node, that is, the representative.
    468 
    469 Let $p$ be the parent of $u$.
    470 
    471 So, to calculate $dp[u]$,
    472 
    473 \begin{align} dp[u] = \begin{cases} dp[p] & \text{if $rep[u] = u$,}\\dp[rep[u]] + cnt[u] & \text{otherwise} \end{cases} \end{align}
    474 
    475 **Second**
    476 
    477 Passing through the representative of a BCC.
    478 
    479 ![](/predownloaded/ec/9c/ec9c017e7b854db44d7d6eae362b557bbd3a4625.png)
    480 
    481 Let's say we have a graph of this type,
    482 
    483 Let's choose our $root$ to be $0$ and look at node $6$.
    484 
    485 There will be no simple path from $root$ to $6$ that uses the edges of the BCC of node $2$.
    486 
    487 Therefore, $dp[6]$ should not include edges from the BCC of node $2$. This is already dealt with by our earlier definition of $dp[u]$!
    488 
    489 **Third**
    490 
    491 The cases of $query(u, v)$.
    492 
    493 Now, $query(u, v)$ depends upon how $u$ and $v$ are connected in the graph. These are some significant cases.
    494 
    495 **Case 1:** $rep[u] = rep[v]$
    496 
    497 That is, $u$ and $v$ are part of the same BCC. Therefore, the answer to $query(u, v)$ is just $cnt[u]$.
    498 
    499 Then, we have two cases concerning $lca(u, v)$.
    500 
    501 **Case 2.1:** We must visit only one node in the BCC of $lca(u, v)$.
    502 
    503 **Case 2.2:** We must visit at least two nodes in the BCC of $lca(u, v)$.
    504 
    505 Example: $u = 6, v = 5$
    506 
    507 ![](/predownloaded/7c/e7/7ce7fce89052bd37eea1a16b55d85ae86a2378e2.png) ![](/predownloaded/58/8f/588f00e732303a74f9bc246227fbb7e2fcf559d9.png)
    508 
    509 In 2.1, in any simple path from $u$ to $v$ we won’t have any edge from the BCC of $lca(u, v)$. Therefore, we don’t need to include $cnt[lca(u, v)]$ in the answer. While in 2.2, those edges will be included.
    510 
    511 In conclusion, in this setup, we need to determine how the simple paths from $u$ to $v$ cross through the BCC of $lca(u,v)$, then the queries will be answered.
    512 
    513 **How to distinguish?**
    514 
    515 We can use binary lifting to determine which node is the lowest ancestor of $u$ in the DFS tree that is a part of the BCC of $lca(u, v)$. Similarly, we can find that node for $v$.
    516 
    517 We can judge which of the above cases any $query(u, v)$ is based on these two nodes.
    518 
    519 There are other ways to distinguish, including using a link-cut tree.
    520 
    521 **Or make a better graph to deal with this…**
    522 
    523 We can create a smart graph to make it so that $query(u, v)$ is $dp[u] + dp[v] - 2 * dp[lca(u, v)] + val[lca(u, v)]$, with no casework involved.
    524 
    525 We will create virtual nodes representing each BCC. Remove all non-bridges from the graph, and connect all nodes of a BCC to its virtual node.
    526 
    527 For example:
    528 
    529 ![](/predownloaded/58/ba/58ba9e88ada5963356ec378e12ac2d9b417fa827.png) --> ![](/predownloaded/d6/3a/d63a895cfc0edf21545beecf1aae374969f916ea.png)
    530 
    531 Here $v$ is the virtual node, and all the nodes present in BCC of $2$ are directly connected to the BCC's virtual node.
    532 
    533 Let us define the value of each actual node to be $0$ and every virtual node to be the count of edges of its BCC. Build an array $dp$ that stores the sum of the values of all vertices from $root$ to the current node.
    534 
    535 You can go back and see how each of the cases would be dealt with by this new graph.