codeforces-scrape

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

1859.md (21958B)


      1 Source: https://codeforces.com/blog/entry/119287
      2 
      3 We hope you liked the problems.
      4 
      5 Task A was invented and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane").
      6 
      7 Task B was invented by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane"), and prepared by [artew](/profile/artew "Specialist artew").
      8 
      9 Task C was invented and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane").
     10 
     11 Task D was invented by [artew](/profile/artew "Specialist artew") and [efimovpaul](/profile/efimovpaul "Candidate Master efimovpaul"), and prepared by [artew](/profile/artew "Specialist artew").
     12 
     13 Task E was invented by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane") and [kristevalex](/profile/kristevalex "Grandmaster kristevalex"), and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane").
     14 
     15 Task F was invented by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane") and [Artyom123](/profile/Artyom123 "Grandmaster Artyom123"), and prepared by [induk_v_tsiane](/profile/induk_v_tsiane "Master induk_v_tsiane").
     16 
     17 [1859A - United We Stand](/contest/1859/problem/A "Codeforces Round 892 (Div. 2)")
     18 
     19 **Hints**
     20 
     21 **Hint 1**
     22 
     23 What does it mean that $A$ divides $B$?
     24 
     25 **Tutorial**
     26 
     27 First, if all numbers are equal, then there is no answer (since $a$ is divisible by $a$, if both arrays are non-empty, then $c_1$ is a divisor of $b_1$).
     28 
     29 Second, if $a$ is divisible by $b$ and they are both natural numbers, then the following equality holds: $b \le a$ (by definition, if $a$ is divisible by $b$, then $a$ can be represented as $k \dot b$, where $k$ is a natural number).
     30 
     31 Now we can place all instances of the smallest number into $b$, and all other numbers into $c$. It can be seen that such a construction always gives a valid answer.
     32 
     33 **Author's code**
     34 
     35 ```
     36 #include <iostream>
     37 #include <algorithm>
     38 #include <vector>
     39 using namespace std;
     40  
     41 void solve() {
     42 	int n = 0; cin >> n; 
     43 	vector<int> inp; inp.assign(n, 0);
     44 	for (auto& x : inp) cin >> x;
     45 	sort(inp.begin(), inp.end());
     46 	if (inp.back() == inp[0]) {
     47 		cout << "-1\n";
     48 		return;
     49 	}
     50 	else {
     51 		int it = 0;
     52 		while (inp[it] == inp[0]) it++;
     53 		cout << it << " " << n - it << "\n";
     54 		for (int j = 0; j < it; ++j) cout << inp[j] << " ";
     55 		for (int j = it; j < n; ++j) cout << inp[j] << " ";
     56 	}
     57 }
     58  
     59 int main() {
     60 	int t = 0; cin >> t;
     61 	while (t--) solve();
     62 	return 0;
     63 }
     64 ```
     65 
     66 [1859B - Olya and Game with Arrays](/contest/1859/problem/B "Codeforces Round 892 (Div. 2)")
     67 
     68 **Hints**
     69 
     70 **Hint 1**
     71 
     72 Do all numbers in a single array really matter?
     73 
     74 **Hint 2**
     75 
     76 If only the first minimum and the second minimum matter, what is the only way to increase a single array's beauty?
     77 
     78 **Hint 3**
     79 
     80 What can we say about the array which will have the smallest number in the end?
     81 
     82 **Tutorial**
     83 
     84 To increase the answer for each array separately, it is necessary to move the minimum to another array. Then, notice that it is optimal to move all the minimums to one array. Let's figure out which array. After moving the minimum from an array, the second minimum in the original array becomes the new minimum. Then, it is easy to notice that it is optimal to move all the minimums to the array with the smallest second minimum. After all the movements, we will have one array where the minimum element is the smallest number among all the arrays, and $n-1$ arrays where the minimum element is the second minimum in the original array.
     85 
     86 Therefore, the answer to the problem will be $M + K - S$, where $M$ is the minimum element among all the arrays, $K$ is the sum of all the second minimums, and $S$ is the smallest second minimum.
     87 
     88 **Author's code**
     89 
     90 ```
     91 #include <iostream>
     92 #include <vector>
     93 #include <algorithm>
     94 #include <numeric>
     95  
     96 using namespace std;
     97  
     98 #define all(v) v.begin(), v.end()
     99  
    100 typedef long long ll;
    101  
    102 const int INF = 1e9 + 7;
    103  
    104 void solve() {
    105     int n;
    106     cin >> n;
    107  
    108     int minn = INF;
    109     vector<int> min2;
    110     for (int i = 0 ; i < n ; i++) {
    111         int m;
    112         cin >> m;
    113         vector<int> v(m);
    114         for (auto &el : v) cin >> el;
    115  
    116         int minel = *min_element(all(v));
    117         minn = min(minn, minel);
    118         v.erase(find(all(v), minel));
    119         min2.push_back(*min_element(all(v)));
    120     }
    121     cout << minn + (ll) accumulate(all(min2), 0ll) - *min_element(all(min2)) << "\n";
    122 }
    123  
    124 signed main() {
    125     ios_base::sync_with_stdio(0);
    126     cin.tie(0);
    127  
    128 #ifdef LOCAL
    129     freopen("a.in", "r", stdin);
    130 #endif
    131  
    132     int t = 1;
    133     cin >> t;
    134     while (t--)
    135         solve();
    136  
    137     return 0;
    138 }
    139 ```
    140 
    141 [1859C - Another Permutation Problem](/contest/1859/problem/C "Codeforces Round 892 (Div. 2)")
    142 
    143 **Hints**
    144 
    145 **Hint 1**
    146 
    147 What if we fix the maximum element in the resulting array?
    148 
    149 **Hint 2**
    150 
    151 Try using greedy.
    152 
    153 **Hint 3**
    154 
    155 Optimize the log factor away by noticing a certain fact.
    156 
    157 **Tutorial**
    158 
    159 Let's fix the maximum element in an array — let it be $M$. Now, let's iterate from $n$ to $1$. Let the current chosen number be $i$. I claim that if we maintain the remaining available numbers to multiply by, then it is optimal to take the maximum such number $x$ that $x * i \le M$.
    160 
    161 Proof: let's say that this is not correct. Then, let's say that we pair $i$ with another number $x1$, and $x$ gets paired with some other number $i1$. Then, $i1 \lt i$, because it was chosen later, and $x1 \lt x$ (otherwise $i * x1 \gt M$). Now let's swap $x$ with $x1$. The sum is increased by $i * x - i * x1 - i1 * x + i1 * x1 = (i - i1)(x - x1) \gt 0$, and all of the numbers are less or equal to $M$.
    162 
    163 Now the task can be solved in $O(N^3logN)$ by simply iterating on the maximum from $N^2$ to $1$, while maintaining the remaining numbers with a set. In order to squeeze it in the TL, you can only consider such maximums that they can be represented as $i * j, 1 \le i, j \le n$.
    164 
    165 In order to optimize it to $O(N^3)$, let's notice that for each number $x$, it can be paired with any number from $1$ to $\frac{M} {x}$. Now just maintain a stack of all available elements at the current moment, add all numbers that possible, and pop the maximum number for all $i$ from $1$ to $N$.
    166 
    167 **Author's code**
    168 
    169 ```
    170 #include <iostream>
    171 #include <algorithm>
    172 #include <set>
    173 #include <stack>
    174 #include <vector>
    175 using namespace std;
    176 void solve() {
    177 	int N = 0; cin >> N;
    178 	int ans = 0;
    179 	vector<int> pr;
    180 	pr.assign(N * N, -1);
    181 	for (int i = 1; i <= N; ++i) {
    182 		for (int j = 1; j <= N; ++j) {
    183 			pr[i * j - 1] = 1;
    184 		}
    185 	}
    186 	for (int mx = N * N; mx >= 1; --mx) {
    187 		if (pr[mx - 1] == -1) continue;
    188 		vector<vector<int>> a;
    189 		int curans = -mx;
    190 		bool br = false;
    191 		a.assign(N, vector<int>());
    192 		for (int j = N; j >= 1; --j) {
    193 			int num = min(mx / j, N);
    194 			if (num < 1) {
    195 				br = true;
    196 				break;
    197 			}
    198 			a[num - 1].push_back(j);
    199 		}
    200 		if (br) break;
    201 		stack<int> s;
    202 		for (int i = 0; i < N; ++i) {
    203 			s.push(i + 1);
    204 			bool brk = false;
    205 			for (auto x : a[i]) {
    206 				if (s.empty()) {
    207 					brk = true; break;
    208 				}
    209 				curans += s.top() * x;
    210 				s.pop();
    211 			}
    212 			if (brk) break;
    213 		}
    214 		ans = max(ans, curans);
    215 	}
    216 	cout << ans << "\n";
    217 }
    218  
    219 int main() {
    220 	ios_base::sync_with_stdio(false);
    221 	cin.tie(nullptr);
    222 	int t = 0; cin >> t;
    223 	while (t--) solve();
    224 	return 0;
    225 }
    226 ```
    227 
    228 [1859D - Andrey and Escape from Capygrad](/contest/1859/problem/D "Codeforces Round 892 (Div. 2)")
    229 
    230 **Hints**
    231 
    232 **Hint 1**
    233 
    234 What if we use greedy a bit?
    235 
    236 **Hint 2**
    237 
    238 Where it is always beneficial to teleport?
    239 
    240 **Hint 3**
    241 
    242 Use scanline
    243 
    244 **Tutorial**
    245 
    246 Statement: It is always beneficial to teleport to point $b_i$.
    247 
    248 Proof: Let's assume that we were able to teleport from point $X$ to the right of $b_i$, but not from $b_i$. Then we used some segment $A$ that covers point $X$, but does not cover point $b$, and ends to the right of $b$. This is a contradiction.
    249 
    250 Let $ans_i$ be the maximum coordinate we can reach while being on segment $i$, and let $p_j$ be the answer to the $j$-th query. Then we notice that the answer to query $p_j = \max(x_j, \max_{i = 1}^n {ans_i \vert l_i \le x_j \le r_i})$.
    251 
    252 We will use the scanline method from the end. Events: $l_i$, $b_i$, $r_i$, $x_j$.
    253 
    254 We notice that events of type $r_i$ are not important to us when scanning from the end (according to statement number 1). It is important for us that we process events of type $b_i$ first, then events of type $x_j$, and then events of type $l_i$ (closing the segment in the scanline).
    255 
    256 We will go through the events of the scanline, processing them in the order of $b_i$, then events of type $x_j$, and then events of type $l_i$.
    257 
    258 We assume that there is a data structure that allows us to add elements, remove elements, and quickly output the maximum.
    259 
    260 * For each event of type $b_i$, update the value of $ans_i$ — take the maximum value of $ans$ of all open segments from the structure.
    261 * For each event of type $x_j$, update the value of $p_j$ — take the maximum value of $ans$ of all open segments from the structure, as well as $x_j$.
    262 * For each event of type $l_i$, remove $ans_i$ from the structure.
    263 
    264 We notice that to solve this problem, we can use the std::multiset} container, which automatically sorts elements in ascending order. We can store in $multiset$ $ans_i$ of all open segments. And then, when processing events, extract the maximum from $multiset$, all operations are performed in $O(\log n)$. This allows us to solve the problem in $O((n + q) \log n)$ time and $O(n)$ memory.
    265 
    266 **Author's code**
    267 
    268 ```
    269 #include <iostream>
    270 #include <vector>
    271 #include <set>
    272 #include <iomanip>
    273 #include <cmath>
    274 #include <algorithm>
    275 #include <map>
    276 #include <stack>
    277 #include <cassert>
    278 #include <unordered_map>
    279 #include <bitset>
    280 #include <random>
    281 #include <unordered_set>
    282 #include <chrono>
    283  
    284 using namespace std;
    285  
    286 #define all(a) a.begin(), a.end()
    287  
    288 void solve() {
    289     int n;
    290     cin >> n;
    291  
    292     vector<int> ans(n);
    293     vector<tuple<int, int, int>> events;
    294     for (int i = 0 ; i < n ; i++) {
    295         int l, r, a, b;
    296         cin >> l >> r >> a >> b;
    297         ans[i] = b;
    298         events.emplace_back(b, 1, i);
    299         events.emplace_back(l, -1, i);
    300     }
    301     int q;
    302     cin >> q;
    303     vector<int> queries(q);
    304     for (int i = 0 ; i < q ; i++) {
    305         int x;
    306         cin >> x;
    307         queries[i] = x;
    308         events.emplace_back(x, 0, i);
    309     }
    310  
    311     sort(all(events));
    312     reverse(all(events));
    313     multiset<int> s;
    314     for (auto [x, type, ind] : events) {
    315         if (type == 1) {
    316             if (!s.empty()) {
    317                 ans[ind] = *s.rbegin();
    318             }
    319             s.insert(ans[ind]);
    320         } else if (type == 0) {
    321             if (!s.empty()) {
    322                 queries[ind] = max(queries[ind], *s.rbegin());
    323             }
    324         } else {
    325             s.extract(ans[ind]);
    326         }
    327     }
    328  
    329     for (auto el : queries)
    330         cout << el << " ";
    331     cout << "\n";
    332 }
    333  
    334 signed main() {
    335     ios_base::sync_with_stdio(false);
    336     cin.tie(nullptr);
    337  
    338     int t = 1;
    339     cin >> t;
    340     while (t--)
    341         solve();
    342  
    343     return 0;
    344 }
    345 ```
    346 
    347 [1859E - Maximum Monogonosity](/contest/1859/problem/E "Codeforces Round 892 (Div. 2)")
    348 
    349 **Hints**
    350 
    351 **Hint 1**
    352 
    353 Maybe we can relax some conditions?
    354 
    355 **Hint 2**
    356 
    357 Do we really need to always correctly calculate all sums?
    358 
    359 **Hint 3**
    360 
    361 Optimize the obvious dp.
    362 
    363 **Tutorial**
    364 
    365 Let's call the value of a segment $[l; r]$ $f(l, r) = abs(a_l - b_r) + abs(a_r - b_l)$.
    366 
    367 Let's write $dp[n1][k1]$ — maximum value of segments of total length $k1$ that end before $n1$.
    368 
    369 The obvious way to recalc is the following:
    370 
    371 $dp[n1][k1] = max(dp[n1 - 1][k1], dp[n1 - l][k1 - l] + f(n1 - l + 1, n1), 1 \le l \le k1)$.
    372 
    373 This works in $O(NK^2)$ and is too slow.
    374 
    375 Now let's consider the following: instead of getting the absolute value of segment $[l; r]$, we consider the maximum of the following four combinations: $b_l - a_r + b_r - a_l$, $b_l - a_r - b_r + a_l$, $-b_l + a_r + b_r - a_l$, $-b_l + a_r - b_r + a_l$. We can see that this always gives us the correct answer to the absolute value, since we check all of the possibilities.
    376 
    377 Now we can look at out dp states as a table, and notice that we recalc over the diagonal (we recalc over all states that have the same value of n1 — k1).
    378 
    379 Now, for each "diagonal", we maintain four maximum combinations: $dp[n1][k1] + b_{k1} + a_{k1}, dp[n1][k1] - b_{k1} + a_{k1}, dp[n1][k1] + b_{k1} - a_{k1}, dp[n1][k1] - b_{k1} - a_{k1}$, and when we want to recalc state $dp[n2][k2]$, we just consider all of the four possibilities.
    380 
    381 **Author's code**
    382 
    383 ```
    384 #include <iostream>
    385 #include <vector>
    386 using namespace std;
    387 const long long INF = 1e18;
    388 #define int long long
    389  
    390 void solve() {
    391 	int N = 0, K = 0; cin >> N >> K;
    392 	vector<int> a;
    393 	vector<int> b;
    394 	a.assign(N, 0);
    395 	b.assign(N, 0);
    396 	for (int i = 0; i < N; ++i) {
    397 		cin >> a[i];
    398 	}
    399 	for (int i = 0; i < N; ++i) {
    400 		cin >> b[i];
    401 	}
    402 	vector<long long> mx1; // max of (b_l + a_l) + corresponding dp
    403 	vector<long long> mx2; // max of (b_l - a_l) + corresponding dp
    404 	vector<long long> mn1; // min of (b_l + a_l) + corresponding dp
    405 	vector<long long> mn2; // min of (b_l - a_l) + corresponding dp
    406 	vector<vector<long long>> dp;
    407 	mx1.assign(N + 1, -INF); mx2.assign(N + 1, -INF);
    408 	mn1.assign(N + 1, INF); mn2.assign(N + 1, INF);
    409 	dp.assign(N + 1, vector<long long>(K + 1, 0));
    410 	for (int i = 0; i <= N; ++i) {
    411 		for (int j = 0; j <= min(i, K); ++j) {
    412 			if (i != 0) dp[i][j] = dp[i - 1][j];
    413 			int diag_val = i - j;
    414 			if (i != 0) {
    415 				dp[i][j] = max(dp[i][j], b[i - 1] + a[i - 1] - mn1[diag_val]);
    416 				dp[i][j] = max(dp[i][j], -b[i - 1] - a[i - 1] + mx1[diag_val]);
    417 				dp[i][j] = max(dp[i][j], a[i - 1] - b[i - 1] - mn2[diag_val]);
    418 				dp[i][j] = max(dp[i][j], b[i - 1] - a[i - 1] + mx2[diag_val]);
    419 			}
    420 			if (i != N) {
    421 				mn1[diag_val] = min(mn1[diag_val], b[i] + a[i] - dp[i][j]);
    422 				mx1[diag_val] = max(mx1[diag_val], b[i] + a[i] + dp[i][j]);
    423 				mn2[diag_val] = min(mn2[diag_val], b[i] - a[i] - dp[i][j]);
    424 				mx2[diag_val] = max(mx2[diag_val], b[i] - a[i] + dp[i][j]);
    425 			}
    426 		}
    427 	}
    428 	cout << dp[N][K] << "\n";
    429 }
    430  
    431  
    432 signed main() {
    433 	int T = 1;
    434 	cin >> T;
    435 	while (T--) {
    436 		solve();
    437 	}
    438 }
    439 ```
    440 
    441 [1859F - Teleportation in Byteland](/contest/1859/problem/F "Codeforces Round 892 (Div. 2)")
    442 
    443 **Hints**
    444 
    445 **Hint 1**
    446 
    447 How many times do we really need to take driving courses?
    448 
    449 **Hint 2**
    450 
    451 Can you think how would an optimal answer path look like?
    452 
    453 **Hint 3**
    454 
    455 Can you recalculate the distances required to get to a city from every vertex?
    456 
    457 **Tutorial**
    458 
    459 Root the tree arbitrarily.
    460 
    461 First, we can notice that there is no need to take driving courses more than $log{maxW}$ times.
    462 
    463 Now, let's iterate for the number of driving courses we take from $0$ to $20$ ($2^{20} \gt 1000000$). For each number we solve separately.
    464 
    465 Let us fix the number of taken as $q$. Now the path looks like the following: we go over the simple path, then we veer off to take courses in some town, then we come back to the path and finish it. Let's call $d[x]$ the minimum distance required to get from $x$ to a town which offers driving courses and then come back to the same town. We can recalculate $d[x]$ with multi-source BFS.
    466 
    467 Now, let's look at the vertex $v1$ on the path, from which we will start going off the path. Then, the cost of the path is $d[v1]$ + distance from $a$ to $v1$ on the original edges (with $c = 1$) + distance from $v1$ to $b$ on the modified edges(with $c = 2^{q}$).
    468 
    469 Now let's look at some cases, let $LCA$ be the LCA of $a$ and $b$, $h1[x]$ — the sum of all original edges from the root downwards to $x$, $h2[x]$ — the sum of all modified edges from the root downwards to $x$.
    470 
    471 If $v1$ is between $LCA$ and $a$, the cost is $h1[a] - h1[v1] + d1[v1] - h2[LCA] + h2[v1] + h2[b] - h2[LCA]$. If $v1$ is between $LCA$ and $a$, the cost is $h1[a] - h1[LCA] + h1[v1] - h1[LCA] + d1[v1] + h2[b] - h2[v1]$. Now we simply need to consider the terms which depend only on $v1$, and then we need to take the maximum value on a path. For that we can use binary lifting, and for LCA as well.
    472 
    473 **Author's code**
    474 
    475 ```
    476 #include <iostream>
    477 #include <iomanip>
    478 #include <fstream>
    479 #include <vector>
    480 #include <numeric>
    481 #include <algorithm>
    482 #include <set>
    483 #include <map>
    484 #include <cmath>
    485 #include <stack>
    486 #include <deque>
    487 #include <string>
    488 #include <ctime>
    489 #include <bitset>
    490 #include <queue>
    491 #include <cassert>
    492 #include<unordered_set>
    493 #include<unordered_map>
    494 #include<string.h>
    495 #include <random>
    496 #include <chrono>
    497 #include <math.h>
    498 using namespace std;
    499 #define pi pair<int, int>
    500 #define ll long long
    501 #define pll pair<ll, ll>
    502 const ll INF = 1e18;
    503 vector<vector<pi>> g;
    504 vector<int> is_special;
    505 vector<vector<int>> bin_lift;
    506 vector<vector<pi>> new_g;
    507 vector<int> tin;
    508 vector<int> tout;
    509 vector<ll> ans;
    510 vector<pi> req;
    511 vector<ll> h_orig;
    512 vector<ll> h_new;
    513 vector<ll> d;
    514 vector<bool> used_bfs;
    515 vector<vector<pll>> bin_lift_2;
    516 vector<int> lc;
    517 vector<int> top_order;
    518 vector<pair<int, int>> pr;
    519 int TIMER = 0;
    520 void DFS(int v, int p) {
    521     top_order.push_back(v);
    522     tin[v] = TIMER++;
    523     bin_lift[v][0] = p;
    524     for (int i = 1; i < 17; ++i) {
    525         if (bin_lift[v][i - 1] == -1) break;
    526         bin_lift[v][i] = bin_lift[bin_lift[v][i - 1]][i - 1];
    527     }
    528     for (auto& x : g[v]) {
    529         if (x.first == p) {
    530             pr.push_back(x);
    531             continue;
    532         }
    533     }
    534     for (auto& x : g[v]) {
    535         if (x.first == p) continue;
    536         h_orig[x.first] = h_orig[v] + x.second;
    537         DFS(x.first, v);
    538     }
    539     tout[v] = TIMER;
    540 }
    541 void BFS(int N) {
    542     priority_queue<pll> q;
    543     for (int i = 0; i < N; ++i) {
    544         if (is_special[i]) {
    545             q.push({ -0, i });
    546             d[i] = 0;
    547         }
    548     }
    549     while (!q.empty()) {
    550         int v = q.top().second; q.pop();
    551         if (used_bfs[v]) continue;
    552         used_bfs[v] = true;
    553         for (auto& x : new_g[v]) {
    554             if (d[x.first] > d[v] + x.second) {
    555                 d[x.first] = d[v] + x.second;
    556                 q.push({ -d[x.first], x.first });
    557             }
    558         }
    559     }
    560 }
    561 inline bool isIn(int a, int b) {
    562     return tin[a] <= tin[b] && tout[a] >= tout[b];
    563 }
    564 int gLCA(int a, int b) {
    565     if (isIn(a, b)) return a;
    566     if (isIn(b, a)) return b;
    567     int cB = b;
    568     for (int i = 16; i >= 0; --i) {
    569         if (bin_lift[cB][i] == -1) continue;
    570         if (!isIn(bin_lift[cB][i], a)) cB = bin_lift[cB][i];
    571     }
    572     return bin_lift[cB][0];
    573 }
    574 ll g1(int a, int LCA) {
    575     ll mn = d[a] + h_new[a] - h_orig[a];
    576     int cK = a;
    577     for (int i = 16; i >= 0; --i) {
    578         if (bin_lift[cK][i] == -1) continue;
    579         if (!isIn(LCA, bin_lift[cK][i])) continue;
    580         mn = min(mn, bin_lift_2[cK][i].first);
    581         cK = bin_lift[cK][i];
    582     }
    583     return mn;
    584 }
    585 ll g2(int a, int LCA) {
    586     ll mn = d[a] + h_orig[a] - h_new[a];
    587     int cK = a;
    588     for (int i = 16; i >= 0; --i) {
    589         if (bin_lift[cK][i] == -1) continue;
    590         if (!isIn(LCA, bin_lift[cK][i])) continue;
    591         mn = min(mn, bin_lift_2[cK][i].second);
    592         cK = bin_lift[cK][i];
    593     }
    594     return mn;
    595 }
    596 void solve() {
    597     top_order.clear();
    598     pr.clear();
    599     int N = 0, T = 0; cin >> N >> T;
    600     g.assign(N, vector<pi>());
    601     for (int j = 0; j < N - 1; ++j) {
    602         int u = 0, v = 0, w = 0; cin >> u >> v >> w;
    603         u--; v--;
    604         g[u].push_back({ v, w }); g[v].push_back({ u, w });
    605     }
    606     is_special.assign(N, 0);
    607     string s = ""; cin >> s;
    608     for (int i = 0; i < N; ++i) is_special[i] = s[i] - '0';
    609     tin.assign(N, 0); tout.assign(N, 0);
    610     bin_lift.assign(N, vector<int>(17, -1));
    611     TIMER = 0;
    612     h_orig.assign(N, 0);
    613     DFS(0, -1);
    614     int Q = 0; cin >> Q;
    615     ans.assign(Q, INF);
    616     req.clear();
    617     lc.clear();
    618     for (int j = 0; j < Q; ++j) {
    619         int u = 0, v = 0; cin >> u >> v;
    620         u--; v--;
    621         req.push_back({ u, v });
    622         lc.push_back(gLCA(u, v));
    623     }
    624     bin_lift_2.assign(N, vector<pll>(17, pll(INF, INF)));
    625     h_new.assign(N, 0);
    626     for (ll level = 1; level <= 20; ++level) {
    627         const int w = (1ll << level);
    628         new_g.assign(N, vector<pi>());
    629         for (int i = 0; i < N; ++i) {
    630             for (int j = 0; j < g[i].size(); ++j) {
    631                 new_g[i].push_back({ g[i][j].first, g[i][j].second + ((g[i][j].second + w - 1) / w) });
    632             }
    633         }
    634         d.assign(N, INF);
    635         used_bfs.assign(N, false);
    636         BFS(N);
    637         h_new[0] = 0;
    638         for (int n = 1; n < N; ++n) {
    639             h_new[top_order[n]] = h_new[pr[n - 1].first] + (pr[n - 1].second + w - 1) / w;
    640             int p = pr[n - 1].first;
    641             int v = top_order[n];
    642             bin_lift_2[v][0] = { d[p] + h_new[p] - h_orig[p], d[p] + h_orig[p] - h_new[p] };
    643             for (int i = 1; i < 17; ++i) {
    644                 if (bin_lift[v][i] == -1) break;
    645                 bin_lift_2[v][i].first = min(bin_lift_2[v][i - 1].first, bin_lift_2[bin_lift[v][i - 1]][i - 1].first);
    646                 bin_lift_2[v][i].second = min(bin_lift_2[v][i - 1].second, bin_lift_2[bin_lift[v][i - 1]][i - 1].second);
    647             }
    648         }
    649         for (int j = 0; j < Q; ++j) {
    650             int a1 = req[j].first; int b1 = req[j].second;
    651             int LCA = lc[j];
    652             ans[j] = min(ans[j], g1(a1, LCA) + h_orig[a1] - h_new[LCA] + h_new[b1] - h_new[LCA] + level * T);
    653             ans[j] = min(ans[j], g2(b1, LCA) + h_orig[a1] - h_orig[LCA] - h_orig[LCA] + h_new[b1] + level * T);
    654         }
    655     }
    656     for (int i = 0; i < Q; ++i) {
    657         ans[i] = min(ans[i], h_orig[req[i].first] + h_orig[req[i].second] - 2 * h_orig[lc[i]]);
    658         cout << ans[i] << "\n";
    659     }
    660 }
    661  
    662 signed main() {
    663     ios_base::sync_with_stdio(false);
    664     cin.tie(0);
    665     cout.tie(0);
    666     cout << setprecision(12);
    667     int T = 1;
    668     cin >> T;
    669     while (T--) {
    670         solve();
    671     }
    672     return 0;
    673 }
    674 ```
    675 
    676 Some notes/challenges:
    677 
    678 * We know about the $O(N^2)$ solution in C, but we did not find a good suitable proof for it (and, using the method, we could achieve faster solutions).
    679 * You can solve $D$ without the constraint that the segments are contained, but that is harder. It is solvable in $(ONlogN)$.
    680 * Thank you all for participating! If you have any complaints/suggestions/advice for future rounds, feel free to share in the comments!