codeforces-scrape

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

1000.md (16932B)


      1 Source: https://codeforces.com/blog/entry/60288
      2 
      3 [1000A - Codehorses T-shirts](/contest/1000/problem/A "Educational Codeforces Round 46 (Rated for Div. 2)")
      4 
      5 **Editorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 #define forn(i, n) for (int i = 0; i < int(n); i++)
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 	int n;
     20 	cin >> n;
     21 	
     22 	vector<string> a(n), b(n);
     23 	forn(i, n) cin >> a[i];
     24 	forn(i, n) cin >> b[i];
     25 	
     26 	map<string, int> cnta, cntb;
     27 	forn(i, n) ++cnta[a[i]];
     28 	forn(i, n) ++cntb[b[i]];
     29 	
     30 	int ans = n;
     31 	for (auto it : cnta) ans -= min(it.second, cntb[it.first]);
     32 	
     33 	cout << ans << endl;
     34 	return 0;
     35 }
     36 ```
     37 
     38 [1000B - Light It Up](/contest/1000/problem/B "Educational Codeforces Round 46 (Rated for Div. 2)")
     39 
     40 **Editorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution**
     45 
     46 ```
     47 #include<bits/stdc++.h>
     48 
     49 using namespace std;
     50 
     51 int n, M;
     52 vector<int> a;
     53 
     54 inline bool read() {
     55 	if(!(cin >> n >> M))
     56 		return false;
     57 	a.assign(n, 0);
     58 	for(int i = 0; i < n; i++)
     59 		scanf("%d", &a[i]);
     60 	return true;
     61 }
     62 
     63 vector<int> f[2];
     64 
     65 inline void solve() {
     66 	a.insert(a.begin(), 0);
     67 	a.push_back(M);
     68 	
     69 	f[0].assign(a.size(), 0);
     70 	f[1].assign(a.size(), 0);
     71 	
     72 	for(int i = int(a.size()) - 2; i >= 0; i--) {
     73 		f[0][i] = f[1][i + 1];
     74 		f[1][i] = (a[i + 1] - a[i]) + f[0][i + 1];
     75 	}
     76 	
     77 	int ans = f[1][0];
     78 	for(int i = 0; i + 1 < int(a.size()); i++) {
     79 		if(a[i + 1] - a[i] < 2)
     80 			continue;
     81 		
     82 		int tp = (i & 1) ^ 1;
     83 		int pSum = f[1][0] - f[tp][i];
     84 		ans = max(ans, pSum + (a[i + 1] - a[i] - 1) + f[tp][i + 1]);
     85 	}
     86 	cout << ans << endl;
     87 }
     88 
     89 int main() {
     90 #ifdef _DEBUG
     91 	freopen("input.txt", "r", stdin);
     92 #endif
     93 	if(read())
     94 		solve();
     95 	return 0;
     96 }
     97 ```
     98 
     99 [1000C - Covered Points Count](/contest/1000/problem/C "Educational Codeforces Round 46 (Rated for Div. 2)")
    100 
    101 **Editorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109 
    110 using namespace std;
    111 
    112 int main() {
    113 #ifdef _DEBUG
    114 	freopen("input.txt", "r", stdin);
    115 //	freopen("output.txt", "w", stdout);
    116 #endif
    117 	
    118 	int n;
    119 	scanf("%d", &n);
    120 	vector<pair<long long, long long>> a(n);
    121 	vector<long long> cval;
    122 	for (auto &i : a) {
    123 		scanf("%lld %lld", &i.first, &i.second);
    124 		cval.push_back(i.first);
    125 		cval.push_back(i.second + 1);
    126 		
    127 	}
    128 	sort(cval.begin(), cval.end());
    129 	cval.resize(unique(cval.begin(), cval.end()) - cval.begin());
    130 	
    131 	vector<int> cnt(2 * n);
    132 	for (auto &i : a) {
    133 		int posl = lower_bound(cval.begin(), cval.end(), i.first) - cval.begin();
    134 		int posr = lower_bound(cval.begin(), cval.end(), i.second + 1) - cval.begin();
    135 		++cnt[posl];
    136 		--cnt[posr];
    137 	}
    138 	for (int i = 1; i < 2 * n; ++i)
    139 		cnt[i] += cnt[i - 1];
    140 		
    141 	vector<long long> ans(n + 1);
    142 	for (int i = 1; i < 2 * n; ++i)
    143 		ans[cnt[i - 1]] += cval[i] - cval[i - 1];
    144 	
    145 	for (int i = 1; i <= n; ++i)
    146 		printf("%lld ", ans[i]);
    147 	puts("");
    148 	
    149 	return 0;
    150 }
    151 ```
    152 
    153 [1000D - Yet Another Problem On a Subsequence](/contest/1000/problem/D "Educational Codeforces Round 46 (Rated for Div. 2)")
    154 
    155 **Editorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution**
    160 
    161 ```
    162 #include <bits/stdc++.h>
    163 
    164 using namespace std;
    165 
    166 const int N = 1009;
    167 const int MOD = 998244353;
    168 
    169 int n;
    170 int a[N];
    171 int dp[N];
    172 int C[N][N];
    173 
    174 int main() {
    175 	for(int i = 0; i < N; ++i){
    176 		C[i][0] = C[i][i] = 1;
    177 		for(int j = 1; j < i; ++j)
    178 			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    179 	}
    180 	
    181 	cin >> n;
    182 	for(int i = 0; i < n; ++i)
    183 		cin >> a[i];
    184 	
    185 	dp[n] = 1;
    186 	for(int i = n - 1; i >= 0; --i){
    187 		if(a[i] <= 0) continue;
    188 		
    189 		for(int j = i + a[i] + 1; j <= n; ++j){
    190 				dp[i] += (dp[j] * 1LL * C[j - i - 1][a[i]]) % MOD;
    191 				dp[i] %= MOD;
    192 		}
    193 	}
    194 
    195 	int sum = 0;
    196 	for(int i = 0; i < n; ++i){
    197 		sum += dp[i];
    198 		sum %= MOD;
    199 	}
    200 	cout << sum << endl;
    201 	
    202     return 0;
    203 }
    204 ```
    205 
    206 [1000E - We Need More Bosses](/contest/1000/problem/E "Educational Codeforces Round 46 (Rated for Div. 2)")
    207 
    208 **Editorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution**
    213 
    214 ```
    215 #include<bits/stdc++.h>
    216 
    217 using namespace std;
    218 
    219 const int N = 500043;
    220 
    221 vector<int> g[N];
    222 vector<int> t[N];
    223 int tin[N], tout[N], fup[N];
    224 int p[N];
    225 int T = 1;
    226 int rnk[N];
    227 vector<pair<int, int> > bridges;
    228 int st;
    229 int d[N];
    230 int n, m;
    231 
    232 int get(int x)
    233 {
    234  	return (p[x] == x ? x : p[x] = get(p[x]));
    235 }
    236 
    237 void link(int x, int y)
    238 {
    239  	x = get(x);
    240  	y = get(y);
    241  	if(x == y) return;
    242  	if(rnk[x] > rnk[y])
    243  		swap(x, y);
    244  	p[x] = y;
    245  	rnk[y] += rnk[x];	
    246 }
    247 
    248 int dfs(int x, int par = -1)
    249 {
    250 	tin[x] = T++;
    251 	fup[x] = tin[x];
    252 	for(auto y : g[x])
    253 	{
    254 	 	if(tin[y] > 0)
    255 	 	{
    256 	 		if(par != y)
    257 	 			fup[x] = min(fup[x], tin[y]);
    258 	 	}
    259 	 	else
    260 	 	{
    261 	 	 	int f = dfs(y, x);
    262 	 	 	fup[x] = min(fup[x], f);
    263 	 	 	if(f > tin[x])
    264 	 	 		bridges.push_back(make_pair(x, y));
    265 	 	 	else
    266 	 	 		link(x, y);
    267 	 	}
    268 	}
    269 	tout[x] = T++;                                      
    270 	return fup[x];
    271 }      
    272 
    273 void build()
    274 {
    275  	for(auto z : bridges)
    276  	{
    277  	 	int x = get(z.first);
    278  	 	int y = get(z.second);
    279  	 	st = x;
    280  	 	t[x].push_back(y);
    281  	 	t[y].push_back(x);
    282  	}
    283 }
    284 
    285 pair<int, int> bfs(int x)
    286 {
    287 	for(int i = 0; i < n; i++)
    288 		d[i] = n + 1;
    289 	d[x] = 0;
    290 	queue<int> q;
    291 	q.push(x);
    292 	int last = 0;
    293 	while(!q.empty())
    294 	{
    295 	 	last = q.front();
    296 	 	q.pop();
    297 	 	for(auto y : t[last])
    298 	 		if(d[y] > d[last] + 1)
    299 	 		{
    300 	 		 	d[y] = d[last] + 1;
    301 	 		 	q.push(y);
    302 	 		}
    303 	}
    304 	return make_pair(last, d[last]);
    305 }
    306 
    307 int main()
    308 {                
    309 	scanf("%d %d", &n, &m);
    310 	for(int i = 0; i < n; i++)
    311 		rnk[i] = 1, p[i] = i;
    312 	for(int i = 0; i < m; i++)
    313 	{
    314 	 	int x, y;
    315 	 	scanf("%d %d", &x, &y);
    316 	 	--x;
    317 	 	--y;
    318 	 	g[x].push_back(y);
    319 	 	g[y].push_back(x);
    320 	}
    321 	dfs(0);
    322 	build();
    323 	pair<int, int> p1 = bfs(st);
    324 	pair<int, int> p2 = bfs(p1.first);
    325 	printf("%d\n", p2.second);
    326 }
    327 ```
    328 
    329 [1000F - One Occurrence](/contest/1000/problem/F "Educational Codeforces Round 46 (Rated for Div. 2)")
    330 
    331 **Editorial**
    332 
    333 Tutorial is loading...
    334 
    335 **Solution with persistent segment tree**
    336 
    337 ```
    338 #include<bits/stdc++.h>
    339 
    340 using namespace std;
    341 
    342 const int INF = int(1e9);
    343 const int N = 500001;
    344 
    345 typedef pair<int, int> pt;
    346 
    347 #define x first
    348 #define y second
    349 #define mp make_pair
    350 
    351 struct node
    352 {
    353  	pt val;
    354 	node* l;
    355 	node* r;
    356 	node() : val(mp(INF, 0)), l(NULL), r(NULL) {};
    357 	node(node* l, node* r) 
    358 	{
    359 	 	this->val = min(l->val, r->val);
    360 		this->l = l;
    361 		this->r = r;
    362 	}
    363 	node(int pos, int val)
    364 	{
    365 	 	this->val = mp(val, pos);
    366 		this->l = NULL;
    367 		this->r = NULL;
    368 	}
    369 };
    370 
    371 typedef node* stree;
    372 
    373 pt query(stree t, int l, int r, int L, int R)
    374 {
    375  	if(L >= R)
    376 		return mp(INF, 0);
    377 	if(l == L && r == R)
    378 		return t->val;
    379 	int mid = (l + r) >> 1;
    380 	pt q1 = query(t->l, l, mid, L, min(mid, R));
    381 	pt q2 = query(t->r, mid, r, max(mid, L), R);
    382 	return min(q1, q2);
    383 }
    384 
    385 stree update(stree t, int l, int r, int pos, int val)
    386 {
    387  	if(l == r - 1)
    388 		return new node(pos, val);
    389 	else
    390 	{
    391 	 	int mid = (l + r) >> 1;
    392 		if(pos < mid)
    393 			return new node(update(t->l, l, mid, pos, val), t->r);
    394 		else
    395 			return new node(t->l, update(t->r, mid, r, pos, val));
    396 	}
    397 }
    398 
    399 stree build(int l, int r)
    400 {
    401  	if(l == r - 1)
    402 		return new node(l, INF);
    403 	else
    404 	{
    405 	 	int mid = (l + r) >> 1;
    406 		return new node(build(l, mid), build(mid, r));
    407 	}
    408 }
    409 
    410 int main()
    411 {
    412  	int n;
    413 	scanf("%d", &n);
    414 	vector<int> a(n);
    415 	for(int i = 0; i < n; i++)
    416 		scanf("%d", &a[i]);
    417 
    418 	vector<int> left(n);
    419 	map<int, int> last;
    420 	for(int i = 0; i < n; i++)
    421 	{
    422 	 	if(!last.count(a[i]))
    423 			left[i] = -1;
    424 		else
    425 			left[i] = last[a[i]];
    426 		last[a[i]] = i;
    427 	}
    428 
    429 	vector<stree> T(n + 1);
    430 	T[0] = build(0, n);
    431 	for(int i = 0; i < n; i++)
    432 	{
    433 		stree cur = T[i];
    434 		if(left[i] != -1)
    435 			cur = update(cur, 0, n, left[i], INF);
    436 		cur = update(cur, 0, n, i, left[i]);
    437 		T[i + 1] = cur;	
    438 	}                      
    439 	
    440 	int q;
    441 	scanf("%d", &q);
    442 	for(int i = 0; i < q; i++)
    443 	{
    444 	 	int l, r;
    445 		scanf("%d %d", &l, &r);
    446 		--l;
    447 		pt ans = query(T[r], 0, n, l, r);
    448 		if(ans.x < l)
    449 			printf("%d\n", a[ans.y]);
    450 		else
    451 			printf("0\n");
    452 	}
    453 }
    454 ```
    455 
    456 **Solution with persistent segment tree (a bit unreadable but runs faster)**
    457 
    458 ```
    459 #include<bits/stdc++.h>
    460 
    461 using namespace std;
    462 
    463 const int INF = int(1e9);
    464 const int N = 500001;
    465 
    466 typedef pair<int, int> pt;
    467 
    468 #define x first
    469 #define y second
    470 #define mp make_pair
    471 
    472 const int M = 60 * N;
    473 
    474 pt bufp[M];
    475 int lf[M];
    476 int rg[M];
    477 int szt = 0;
    478 
    479 int newnode(pt val)
    480 {
    481 	bufp[szt] = val;
    482 	return szt++;
    483 }
    484 
    485 int newnode(int l, int r)
    486 {
    487  	lf[szt] = l;
    488 	rg[szt] = r;
    489 	if(bufp[l].x < bufp[r].x)
    490 	    bufp[szt] = bufp[l];
    491 	else
    492 	    bufp[szt] = bufp[r];
    493 	return szt++;
    494 }
    495 
    496 pt curans;
    497 
    498 void query(int t, int l, int r, int L, int R)
    499 {
    500  	if(L >= R)
    501 		return;
    502 	if(l == L && r == R)
    503 	{
    504 	    if(bufp[t].x < curans.x)
    505 	        curans = bufp[t];
    506 	    return;
    507 	}
    508 	int mid = (l + r) >> 1;
    509 	query(lf[t], l, mid, L, min(mid, R));
    510 	query(rg[t], mid, r, max(mid, L), R);
    511 }
    512 
    513 int update(int t, int l, int r, int pos, int val)
    514 {
    515  	if(l == r - 1)
    516 		return newnode(mp(val, pos));
    517 	else
    518 	{
    519 	 	int mid = (l + r) >> 1;
    520 		if(pos < mid)
    521 			return newnode(update(lf[t], l, mid, pos, val), rg[t]);
    522 		else
    523 			return newnode(lf[t], update(rg[t], mid, r, pos, val));
    524 	}
    525 }
    526 
    527 int build(int l, int r)
    528 {
    529  	if(l == r - 1)
    530 		return newnode(mp(INF, l));
    531 	else
    532 	{
    533 	 	int mid = (l + r) >> 1;
    534 		return newnode(build(l, mid), build(mid, r));
    535 	}
    536 }
    537 
    538 int last[N];
    539 
    540 int main()
    541 {
    542  	int n;
    543 	scanf("%d", &n);
    544 	vector<int> a(n);
    545 	for(int i = 0; i < n; i++)
    546 		scanf("%d", &a[i]);
    547 
    548 	vector<int> left(n);
    549 	for(int i = 0; i < N; i++)
    550 	    last[i] = -1;
    551 	for(int i = 0; i < n; i++)
    552 	{
    553 	 	left[i] = last[a[i]];
    554 		last[a[i]] = i;
    555 	}
    556 
    557 	vector<int> T(n + 1);
    558 	T[0] = build(0, n);
    559 	for(int i = 0; i < n; i++)
    560 	{
    561 		int cur = T[i];
    562 		if(left[i] != -1)
    563 			cur = update(cur, 0, n, left[i], INF);
    564 		cur = update(cur, 0, n, i, left[i]);
    565 		T[i + 1] = cur;	
    566 	}                      
    567 	
    568 	int q;
    569 	scanf("%d", &q);
    570 	for(int i = 0; i < q; i++)
    571 	{
    572 	 	int l, r;
    573 		scanf("%d %d", &l, &r);
    574 		--l;
    575 		curans = mp(INF, 0);
    576 		query(T[r], 0, n, l, r);
    577 		if(curans.x < l)
    578 			printf("%d\n", a[curans.y]);
    579 		else
    580 			printf("0\n");
    581 	}
    582 }
    583 ```
    584 
    585 **Solution with standard segment tree**
    586 
    587 ```
    588 #include <bits/stdc++.h>
    589  
    590 using namespace std;
    591  
    592 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    593 #define x first
    594 #define y second
    595 
    596 const int N = 500 * 1000 + 13;
    597 const int INF = 1e9;
    598 
    599 pair<pair<int, int>, int> t[4 * N];
    600 
    601 void build(int v, int l, int r){
    602 	if (l == r - 1){
    603 		t[v] = make_pair(make_pair(INF, INF), l);
    604 		return;
    605 	}
    606 	
    607 	int m = (l + r) / 2;
    608 	
    609 	build(v * 2, l, m);
    610 	build(v * 2 + 1, m, r);
    611 	
    612 	t[v] = min(t[v * 2], t[v * 2 + 1]);
    613 }
    614 
    615 void update(int v, int l, int r, int pos, int prv, int nxt){
    616 	if (l == r - 1){
    617 		t[v].x = make_pair(nxt, prv);
    618 		return;
    619 	}
    620 	
    621 	int m = (l + r) / 2;
    622 	
    623 	if (pos < m)
    624 		update(v * 2, l, m, pos, prv, nxt);
    625 	else
    626 		update(v * 2 + 1, m, r, pos, prv, nxt);
    627 	
    628 	t[v] = min(t[v * 2], t[v * 2 + 1]);
    629 }
    630 
    631 pair<pair<int, int>, int> get(int v, int l, int r, int L, int R){
    632 	if (L >= R)
    633 		return make_pair(make_pair(INF, INF), -1);
    634 	
    635 	if (l == L && r == R)
    636 		return t[v];
    637 	
    638 	int m = (l + r) / 2;
    639 	
    640 	return min(get(v * 2, l, m, L, min(m, R)), get(v * 2 + 1, m, r, max(m, L), R));
    641 }
    642 
    643 int n, m;
    644 int a[N];
    645 pair<pair<int, int>, int> q[N];
    646 int pos[N];
    647 int ans[N];
    648 
    649 bool comp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){
    650 	return a.x.y < b.x.y;
    651 }
    652 
    653 int main() {
    654 	memset(pos, -1, sizeof(pos));
    655 	scanf("%d", &n);
    656 	forn(i, n) scanf("%d", &a[i]);
    657 	scanf("%d", &m);
    658 	forn(i, m){
    659 		scanf("%d%d", &q[i].x.x, &q[i].x.y);
    660 		--q[i].x.x, --q[i].x.y;
    661 		q[i].y = i;
    662 	}
    663 	sort(q, q + m, comp);
    664 	
    665 	build(1, 0, n);
    666 	int lst = -1;
    667 	forn(i, m){
    668 		int l = q[i].x.x;
    669 		int r = q[i].x.y;
    670 		
    671 		for (int j = lst + 1; j <= r; ++j){
    672 			if (pos[a[j]] != -1)
    673 				update(1, 0, n, pos[a[j]], -INF, j);
    674 			update(1, 0, n, j, pos[a[j]], -INF);
    675 			pos[a[j]] = j;
    676 		}
    677 		
    678 		auto it = get(1, 0, n, l, r + 1);
    679 		
    680 		if (it.y == -1 || it.x.x != -INF || it.x.y >= l){
    681 			ans[q[i].y] = 0;
    682 		}
    683 		else{
    684 			ans[q[i].y] = a[it.y];
    685 		}
    686 		
    687 		lst = r;
    688 	}
    689 	
    690 	forn(i, m)
    691 		printf("%d\n", ans[i]);
    692 	
    693 	return 0;
    694 }
    695 ```
    696 
    697 **Mo-based solution**
    698 
    699 ```
    700 #include <bits/stdc++.h>
    701  
    702 using namespace std;
    703  
    704 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    705 #define x first
    706 #define y second
    707 
    708 const int N = 500 * 1000 + 13;
    709 const int P = 800;
    710 const int INF = 1e9;
    711 
    712 bool comp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){
    713 	int num = a.x.x / P;
    714 	if (num != b.x.x / P)
    715 		return a.x.x < b.x.x;
    716 	if (num & 1)
    717 		return a.x.y < b.x.y;
    718 	return a.x.y > b.x.y;
    719 }
    720 
    721 int val[N];
    722 int cnt[N];
    723 int bl[P];
    724 int tot;
    725 
    726 inline void add(int x){
    727 	++cnt[x];
    728 	if (cnt[x] == 1){
    729 		++val[x];
    730 		++bl[x / P];
    731 		++tot;
    732 	}
    733 	else if (cnt[x] == 2){
    734 		--val[x];
    735 		--bl[x / P];
    736 		--tot;
    737 	}
    738 }
    739 
    740 inline void sub(int x){
    741 	--cnt[x];
    742 	if (cnt[x] == 1){
    743 		++val[x];
    744 		++bl[x / P];
    745 		++tot;
    746 	}
    747 	else if (cnt[x] == 0){
    748 		--val[x];
    749 		--bl[x / P];
    750 		--tot;
    751 	}
    752 }
    753 
    754 int get(){
    755 	if (tot == 0) 
    756 		return 0;
    757 	
    758 	forn(i, P){
    759 		if (bl[i] > 0){
    760 			for (int j = i * P;; ++j){
    761 				if (val[j]){
    762 					return j;
    763 				}
    764 			}
    765 		}
    766 	}
    767 	
    768 	assert(false);
    769 }
    770 
    771 int n, m;
    772 int a[N], ans[N];
    773 pair<pair<int, int>, int> q[N];
    774 
    775 int main() {
    776 	scanf("%d", &n);
    777 	forn(i, n) scanf("%d", &a[i]);
    778 	scanf("%d", &m);
    779 	forn(i, m){
    780 		scanf("%d%d", &q[i].x.x, &q[i].x.y);
    781 		--q[i].x.x, --q[i].x.y;
    782 		q[i].y = i;
    783 	}
    784 	sort(q, q + m, comp);
    785 	
    786 	int l = 0, r = -1;
    787 	
    788 	forn(i, m){
    789 		int L = q[i].x.x;
    790 		int R = q[i].x.y;
    791 		
    792 		while (r < R){
    793 			++r;
    794 			add(a[r]);
    795 		}
    796 		
    797 		while (r > R){
    798 			sub(a[r]);
    799 			--r;
    800 		}
    801 		
    802 		while (l > L){
    803 			--l;
    804 			add(a[l]);
    805 		}
    806 		
    807 		while (l < L){
    808 			sub(a[l]);
    809 			++l;
    810 		}
    811 		
    812 		ans[q[i].y] = get();
    813 	}
    814 	
    815 	forn(i, m)
    816 		printf("%d\n", ans[i]);
    817 	
    818 	return 0;
    819 }
    820 ```
    821 
    822 [1000G - Two-Paths](/contest/1000/problem/G "Educational Codeforces Round 46 (Rated for Div. 2)")
    823 
    824 **Editorial**
    825 
    826 Tutorial is loading...
    827 
    828 **Solution**
    829 
    830 ```
    831 #include<bits/stdc++.h>
    832 
    833 using namespace std;
    834 
    835 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    836 
    837 #define sz(a) int((a).size())
    838 #define all(a) (a).begin(), (a).end()
    839 
    840 #define x first
    841 #define y second
    842 
    843 typedef long long li;
    844 typedef long double ld;
    845 typedef pair<int, int> pt;
    846 
    847 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    848 	return out << "(" << p.x << ", " << p.y << ")";
    849 }
    850 
    851 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    852 	out << "[";
    853 	fore(i, 0, sz(v)) {
    854 		if(i) out << ", ";
    855 		out << v[i];
    856 	}
    857 	return out << "]";
    858 }
    859 
    860 const int M = 400 * 1000 + 555;
    861 const int N = 300 * 1000 + 555;
    862 const int LOGN = 19;
    863 
    864 int n, m, a[N];
    865 vector<pt> g[N];
    866 
    867 inline bool read() {
    868 	if(!(cin >> n >> m))
    869 		return false;
    870 	fore(i, 0, n)
    871 		assert(scanf("%d", &a[i]) == 1);
    872 	fore(i, 0, n - 1) {
    873 		int u, v, w;
    874 		assert(scanf("%d%d%d", &u, &v, &w) == 3);
    875 		u--, v--;
    876 		
    877 		g[u].emplace_back(v, w);
    878 		g[v].emplace_back(u, w);
    879 	}
    880 	fore(i, 0, n)
    881 		sort(all(g[i]));
    882 	return true;
    883 }
    884 
    885 int tin[N], tout[N], T = 0;
    886 int p[N][LOGN];
    887 
    888 int h[N];
    889 li d1[N];
    890 
    891 void calc1(int v, int pr) {
    892 	tin[v] = T++;
    893 	p[v][0] = pr;
    894 	fore(st, 1, LOGN)
    895 		p[v][st] = p[p[v][st - 1]][st - 1];
    896 	
    897 	d1[v] = a[v];
    898 	fore(i, 0, sz(g[v])) {
    899 		int to = g[v][i].x;
    900 		int w = g[v][i].y;
    901 		
    902 		if(to == pr)
    903 			continue;
    904 
    905 		h[to] = h[v] + 1;
    906 		calc1(to, v);
    907 		d1[v] += max(0ll, d1[to] - 2ll * w);
    908 	}
    909 	tout[v] = T++;
    910 }
    911 
    912 li dp[N];
    913 vector<li> dto[N];
    914 
    915 void calcRRT(int v) {
    916 	dp[v] = a[v];
    917 	dto[v].assign(sz(g[v]), 0ll);
    918 	
    919 	fore(i, 0, sz(g[v])) {
    920 		int to = g[v][i].x;
    921 		int w = g[v][i].y;
    922 		
    923 		li curVal = max(0ll, d1[to] - 2ll * w);
    924 		dp[v] += curVal;
    925 		dto[v][i] = curVal;
    926 	}
    927 	
    928 	fore(i, 0, sz(g[v])) {
    929 		int to = g[v][i].x;
    930 		if(h[to] < h[v])
    931 			continue;
    932 		
    933 		li tmp = d1[v];
    934 		d1[v] = dp[v] - dto[v][i];
    935 		calcRRT(to);
    936 		d1[v] = tmp;
    937 	}
    938 }
    939 
    940 inline bool isP(int l, int v) {
    941 	return tin[l] <= tin[v] && tout[v] <= tout[l];
    942 }
    943 
    944 int lca(int u, int v) {
    945 	if(isP(u, v)) return u;
    946 	if(isP(v, u)) return v;
    947 	
    948 	for(int st = LOGN - 1; st >= 0; st--)
    949 		if(!isP(p[v][st], u))
    950 			v = p[v][st];
    951 	return p[v][0];
    952 }
    953 
    954 li getDto(int v, int to) {
    955 	int pos = int(lower_bound(all(g[v]), pt(to, -1)) - g[v].begin());
    956 	if(pos >= sz(g[v]) || g[v][pos].x != to)
    957 		return 0;
    958 	return dto[v][pos];
    959 }
    960 
    961 li f[N];
    962 
    963 inline void inc(int pos, li val) {
    964 	for(; pos < N; pos |= pos + 1)
    965 		f[pos] += val;
    966 }
    967 
    968 inline li sum(int pos) {
    969 	li ans = 0;
    970 	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
    971 		ans += f[pos];
    972 	return ans;
    973 }
    974 
    975 inline li getSum(int l, int r) {
    976 	return sum(r) - sum(l);
    977 }
    978 
    979 li ans[M];
    980 vector<pt> qs[N];
    981 
    982 void calcAns(int v) {
    983 	li vAdd = dp[v] - getDto(v, p[v][0]);
    984 	inc(h[v], vAdd);
    985 	
    986 	for(pt &q : qs[v]) {
    987 		int up = q.x, id = q.y;
    988 		ans[id] += getSum(h[up] - 1, h[v]) + getDto(up, p[up][0]);
    989 	}
    990 	
    991 	fore(i, 0, sz(g[v])) {
    992 		int to = g[v][i].x;
    993 		int w = g[v][i].y;
    994 		if(h[to] < h[v])
    995 			continue;
    996 		
    997 		li curSub = dto[v][i] + w;
    998 		inc(h[v], -curSub);
    999 		
   1000 		calcAns(to);
   1001 		inc(h[v], +curSub);
   1002 	}
   1003 	inc(h[v], -vAdd);
   1004 }
   1005 
   1006 inline void solve() {
   1007 	T = 0;
   1008 	h[0] = 0;
   1009 	calc1(0, 0);
   1010 	calcRRT(0);
   1011 	
   1012 	fore(i, 0, m) {
   1013 		int u, v;
   1014 		assert(scanf("%d%d", &u, &v) == 2);
   1015 		u--, v--;
   1016 		
   1017 		int l = lca(u, v);		
   1018 		ans[i] = -dp[l];
   1019 		
   1020 		qs[u].emplace_back(l, i);
   1021 		qs[v].emplace_back(l, i);
   1022 	}
   1023 	
   1024 	calcAns(0);
   1025 	fore(i, 0, m)
   1026 		printf("%lld\n", ans[i]);
   1027 }
   1028 
   1029 int main() {
   1030 #ifdef _DEBUG
   1031 	freopen("input.txt", "r", stdin);
   1032 	int tt = clock();
   1033 #endif
   1034 	cout << fixed << setprecision(15);
   1035 	
   1036 	if(read()) {
   1037 		solve();
   1038 		
   1039 #ifdef _DEBUG
   1040 		cerr << "TIME = " << clock() - tt << endl;
   1041 		tt = clock();
   1042 #endif
   1043 	}
   1044 	return 0;
   1045 }
   1046 ```