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  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  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  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  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   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  -->  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.