Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解

admin2024-09-04  16

A. Dora’s Set

Problem Statement

Dora has a set s s s containing integers. In the beginning, she will put all integers in [ l , r ] [l, r] [l,r] into the set s s s. That is, an integer x x x is initially contained in the set if and only if l ≤ x ≤ r l \leq x \leq r lxr. Then she allows you to perform the following operations:

  • Select three distinct integers a a a, b b b, and c c c from the set s s s, such that gcd ⁡ ( a , b ) = gcd ⁡ ( b , c ) = gcd ⁡ ( a , c ) = 1 † \gcd(a, b) = \gcd(b, c) = \gcd(a, c) = 1^\dagger gcd(a,b)=gcd(b,c)=gcd(a,c)=1.
  • Then, remove these three integers from the set s s s.

What is the maximum number of operations you can perform?

† ^\dagger Recall that gcd ⁡ ( x , y ) \gcd(x, y) gcd(x,y) means the greatest common divisor of integers x x x and y y y.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 500 1 \leq t \leq 500 1t500) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers l l l and r r r ( 1 ≤ l ≤ r ≤ 1000 1 \leq l \leq r \leq 1000 1lr1000) — the range of integers in the initial set.

Output

For each test case, output a single integer — the maximum number of operations you can perform.

Example

input
8
1 3
3 7
10 21
2 8
51 60
2 15
10 26
1 1000
output
1
1
3
1
2
3
4
250

Note

In the first test case, you can choose a = 1 a = 1 a=1, b = 2 b = 2 b=2, c = 3 c = 3 c=3 in the only operation, since gcd ⁡ ( 1 , 2 ) = gcd ⁡ ( 2 , 3 ) = gcd ⁡ ( 1 , 3 ) = 1 \gcd(1, 2) = \gcd(2, 3) = \gcd(1, 3) = 1 gcd(1,2)=gcd(2,3)=gcd(1,3)=1, and then there are no more integers in the set, so no more operations can be performed.

In the second test case, you can choose a = 3 a = 3 a=3, b = 5 b = 5 b=5, c = 7 c = 7 c=7 in the only operation.

In the third test case, you can choose a = 11 a = 11 a=11, b = 19 b = 19 b=19, c = 20 c = 20 c=20 in the first operation, a = 13 a = 13 a=13, b = 14 b = 14 b=14, c = 15 c = 15 c=15 in the second operation, and a = 10 a = 10 a=10, b = 17 b = 17 b=17, c = 21 c = 21 c=21 in the third operation. After the three operations, the set s s s contains the following integers: 12 12 12, 16 16 16, 18 18 18. It can be proven that it’s impossible to perform more than 3 3 3 operations.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
 
void solve() {
	int l, r;
	cin >> l >> r;
 
	int res = (r - l + 1) / 4;
	if ((r - l + 1) % 4 == 3 && ((r - 2) & 1)) res ++;
	cout << res << endl;
}
 
signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
 
	int dt;
	cin >> dt;
 
	while (dt --)
		solve();
 
	return 0;
}

B. Index and Maximum Value

Problem Statement

After receiving yet another integer array a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an at her birthday party, Index decides to perform some operations on it.

Formally, there are m m m operations that she is going to perform in order. Each of them belongs to one of the two types:

  • +   l   r \texttt{+ l r} + l r. Given two integers l l l and r r r, for all 1 ≤ i ≤ n 1 \leq i \leq n 1in such that l ≤ a i ≤ r l \leq a_i \leq r lair, set a i : = a i + 1 a_i := a_i + 1 ai:=ai+1.
  • -   l   r \texttt{- l r} - l r. Given two integers l l l and r r r, for all 1 ≤ i ≤ n 1 \leq i \leq n 1in such that l ≤ a i ≤ r l \leq a_i \leq r lair, set a i : = a i − 1 a_i := a_i - 1 ai:=ai1.

For example, if the initial array a = [ 7 , 1 , 3 , 4 , 3 ] a = [7, 1, 3, 4, 3] a=[7,1,3,4,3], after performing the operation +   2   4 \texttt{+} \space 2 \space 4 + 2 4, the array a = [ 7 , 1 , 4 , 5 , 4 ] a = [7, 1, 4, 5, 4] a=[7,1,4,5,4]. Then, after performing the operation -   1   10 \texttt{-} \space 1 \space 10 - 1 10, the array a = [ 6 , 0 , 3 , 4 , 3 ] a = [6, 0, 3, 4, 3] a=[6,0,3,4,3].

Index is curious about the maximum value in the array a a a. Please help her find it after each of the m m m operations.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 2 ⋅ 1 0 4 1 \leq t \leq 2 \cdot 10^4 1t2104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n n n and m m m ( 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105, 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1m105) — the length of the array and the number of operations.

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an ( 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1ai109) — the initial array a a a.

Then m m m lines follow, each line corresponds to the operation, in the following format: c   l   r \texttt{c l r} c l r ( c ∈ { + , - } c \in \{\texttt +, \texttt -\} c{+,-}, l l l and r r r are integers, 1 ≤ l ≤ r ≤ 1 0 9 1 \leq l \leq r \leq 10^9 1lr109) — the description of the operation.

Note that the elements a i a_i ai may not satisfy 1 ≤ a i ≤ 1 0 9 1\le a_i\le 10^9 1ai109 after some operations, as it is shown in the example.

It is guaranteed that the sum of n n n over all test cases does not exceed 1 0 5 10^5 105, and the sum of m m m over all test cases does not exceed 1 0 5 10^5 105.

Output

For each test case, output one single line containing m m m integers, with the i i i-th of them describing the maximum value of the array after the i i i-th operation.

Example

input
5
5 5
1 2 3 2 1
+ 1 3
- 2 3
+ 1 2
+ 2 4
- 6 8
5 5
1 3 3 4 5
+ 1 4
+ 2 3
- 4 5
- 3 3
- 2 6
5 5
1 1 1 1 1
+ 2 3
- 4 5
+ 1 6
- 2 5
+ 1 8
1 1
1
- 1 1
1 1
1000000000
+ 1000000000 1000000000
output
4 4 4 5 5
5 5 4 4 3
1 1 2 1 2
0
1000000001

Note

In the first test case, the process of the operations is listed below:

  • After the first operation, the array becomes equal [ 2 , 3 , 4 , 3 , 2 ] [2,3,4,3,2] [2,3,4,3,2]. The maximum value is 4 4 4.
  • After the second operation, the array becomes equal [ 1 , 2 , 4 , 2 , 1 ] [1,2,4,2,1] [1,2,4,2,1]. The maximum value is 4 4 4.
  • After the third operation, the array becomes equal [ 2 , 3 , 4 , 3 , 2 ] [2,3,4,3,2] [2,3,4,3,2]. The maximum value is 4 4 4.
  • After the fourth operation, the array becomes equal [ 3 , 4 , 5 , 4 , 3 ] [3,4,5,4,3] [3,4,5,4,3]. The maximum value is 5 5 5.
  • After the fifth operation, the array becomes equal [ 3 , 4 , 5 , 4 , 3 ] [3,4,5,4,3] [3,4,5,4,3]. The maximum value is 5 5 5.

In the second test case, the process of the operations is listed below:

  • After the first operation, the array becomes equal [ 2 , 4 , 4 , 5 , 5 ] [2,4,4,5,5] [2,4,4,5,5]. The maximum value is 5 5 5.
  • After the second operation, the array becomes equal [ 3 , 4 , 4 , 5 , 5 ] [3,4,4,5,5] [3,4,4,5,5]. The maximum value is 5 5 5.
  • After the third operation, the array becomes equal [ 3 , 3 , 3 , 4 , 4 ] [3,3,3,4,4] [3,3,3,4,4]. The maximum value is 4 4 4.
  • After the fourth operation, the array becomes equal [ 2 , 2 , 2 , 4 , 4 ] [2,2,2,4,4] [2,2,2,4,4]. The maximum value is 4 4 4.
  • After the fifth operation, the array becomes equal [ 1 , 1 , 1 , 3 , 3 ] [1,1,1,3,3] [1,1,1,3,3]. The maximum value is 3 3 3.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
 
void solve() {
	int n, m;
	cin >> n >> m;
	std::vector<int> a(n);
	int mx = 0;
	for (int i = 0; i < n; i ++)
		cin >> a[i], mx = max(mx, a[i]);
 
	while (m -- ) {
		char op;
		int l, r;
		cin >> op >> l >> r;
 
		if (op == '+') {
			if (mx >= l && mx <= r) mx ++;
		} else {
			if (mx >= l && mx <= r) mx --;
		}
		cout << mx << " ";
	}
	cout << endl;
}
 
signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
 
	int dt;
	cin >> dt;
 
	while (dt --)
		solve();
 
	return 0;
}

C. Dora and C++

Problem Statement

Dora has just learned the programming language C++!

However, she has completely misunderstood the meaning of C++. She considers it as two kinds of adding operations on the array c c c with n n n elements. Dora has two integers a a a and b b b. In one operation, she can choose one of the following things to do.

  • Choose an integer i i i such that 1 ≤ i ≤ n 1 \leq i \leq n 1in, and increase c i c_i ci by a a a.
  • Choose an integer i i i such that 1 ≤ i ≤ n 1 \leq i \leq n 1in, and increase c i c_i ci by b b b.

Note that a a a and b b b are constants, and they can be the same.

Let’s define a range of array d d d as max ⁡ ( d i ) − min ⁡ ( d i ) \max(d_i) - \min(d_i) max(di)min(di). For instance, the range of the array [ 1 , 2 , 3 , 4 ] [1, 2, 3, 4] [1,2,3,4] is 4 − 1 = 3 4 - 1 = 3 41=3, the range of the array [ 5 , 2 , 8 , 2 , 2 , 1 ] [5, 2, 8, 2, 2, 1] [5,2,8,2,2,1] is 8 − 1 = 7 8 - 1 = 7 81=7, and the range of the array [ 3 , 3 , 3 ] [3, 3, 3] [3,3,3] is 3 − 3 = 0 3 - 3 = 0 33=0.

After any number of operations (possibly, 0 0 0), Dora calculates the range of the new array. You need to help Dora minimize this value, but since Dora loves exploring all by herself, you only need to tell her the minimized value.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1t104) — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers n n n, a a a, and b b b ( 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105, 1 ≤ a , b ≤ 1 0 9 1 \leq a, b \leq 10^9 1a,b109) — the length of the array c c c and the constant values, respectively.

The second line of each test case contains n n n integers c 1 , c 2 , … , c n c_1, c_2, \ldots, c_n c1,c2,,cn ( 1 ≤ c i ≤ 1 0 9 1 \leq c_i \leq 10^9 1ci109) — the initial elements of the array c c c.

It is guaranteed that the sum of n n n over all test cases does not exceed 1 0 5 10^5 105.

Output

For each test case, output a single integer — the minimum possible range of the array after any number of operations.

Example

input
10
4 5 5
1 3 4 4
4 2 3
1 3 4 6
4 7 7
1 1 2 6
3 15 9
1 9 5
3 18 12
1 4 5
7 27 36
33 13 23 12 35 24 41
10 6 9
15 5 6 9 8 2 12 15 3 8
2 1 1000000000
1 1000000000
6 336718728 709848696
552806726 474775724 15129785 371139304 178408298 13106071
6 335734893 671469786
138885253 70095920 456876775 9345665 214704906 375508929
output
3
0
3
2
3
5
1
0
17
205359241

Note

In the first test case, we can increase c 1 = 1 c_1 = 1 c1=1 by a = 5 a = 5 a=5. The array c c c will become [ 6 , 3 , 4 , 4 ] [6, 3, 4, 4] [6,3,4,4], and the range is 3 3 3. Note that there is more than one way to reach the answer.

In the second test case, we can increase c 1 = 1 c_1 = 1 c1=1 by a = 2 a = 2 a=2 and then increase c 1 = 3 c_1 = 3 c1=3 by b = 3 b = 3 b=3. Also, we can increase c 2 = 3 c_2 = 3 c2=3 by b = 3 b = 3 b=3 and increase c 3 = 4 c_3 = 4 c3=4 by a = 2 a = 2 a=2. The array c c c will become [ 6 , 6 , 6 , 6 ] [6, 6, 6, 6] [6,6,6,6], and the range is 0 0 0.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
	int n, m;
	cin >> n >> m;
	std::vector<PII> a(n);
	for (int i = 0; i < n; i ++) cin >> a[i].fi;
	for (int i = 0; i < n; i ++) cin >> a[i].se;
	sort(a.begin(), a.end());

	int res = min(m / a[n - 1].fi, a[n - 1].se) * a[n - 1].fi;
	for (int i = 0; i < n - 1; i ++) {
		if (a[i + 1].fi > a[i].fi + 1) { res = max(res, min(m / a[i].fi, a[i].se) * a[i].fi); continue;}
		int c1 = min(a[i].se, m / a[i].fi), c2 = min(a[i + 1].se, (m - c1 * a[i].fi) / a[i + 1].fi);
		int add = min({a[i + 1].se - c2, c1, m - c1 * a[i].fi - c2 * a[i + 1].fi});
		res = max(res, c1 * a[i].fi + c2 * a[i + 1].fi + add);
	}
	cout << res << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

D. Iris and Game on the Tree

Problem Statement

Iris has a tree rooted at vertex 1 1 1. Each vertex has a value of 0 \mathtt 0 0 or 1 \mathtt 1 1.

Let’s consider a leaf of the tree (the vertex 1 1 1 is never considered a leaf) and define its weight. Construct a string formed by the values of the vertices on the path starting at the root and ending in this leaf. Then the weight of the leaf is the difference between the number of occurrences of 10 \mathtt{10} 10 and 01 \mathtt{01} 01 substrings in it.

Take the following tree as an example. Green vertices have a value of 1 \mathtt 1 1 while white vertices have a value of 0 \mathtt 0 0.
Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解,在这里插入图片描述,第1张

  • Let’s calculate the weight of the leaf 5 5 5: the formed string is 10110 \mathtt{10110} 10110. The number of occurrences of substring 10 \mathtt{10} 10 is 2 2 2, the number of occurrences of substring 01 \mathtt{01} 01 is 1 1 1, so the difference is 2 − 1 = 1 2 - 1 = 1 21=1.
  • Let’s calculate the weight of the leaf 6 6 6: the formed string is 101 \mathtt{101} 101. The number of occurrences of substring 10 \mathtt{10} 10 is 1 1 1, the number of occurrences of substring 01 \mathtt{01} 01 is 1 1 1, so the difference is 1 − 1 = 0 1 - 1 = 0 11=0.

The score of a tree is defined as the number of leaves with non-zero weight in the tree.

But the values of some vertices haven’t been decided and will be given to you as ? \texttt{?} ?. Filling the blanks would be so boring, so Iris is going to invite Dora to play a game. On each turn, one of the girls chooses any of the remaining vertices with value ? \texttt{?} ? and changes its value to 0 \mathtt{0} 0 or 1 \mathtt{1} 1, with Iris going first. The game continues until there are no vertices with value ? \mathtt{?} ? left in the tree. Iris aims to maximize the score of the tree, while Dora aims to minimize that.

Assuming that both girls play optimally, please determine the final score of the tree.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 5 ⋅ 1 0 4 1 \leq t \leq 5\cdot 10^4 1t5104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n n n ( 2 ≤ n ≤ 1 0 5 2 \leq n \leq 10^5 2n105) — the number of vertices in the tree.

The following n − 1 n - 1 n1 lines each contain two integers u u u and v v v ( 1 ≤ u , v ≤ n 1 \leq u, v \leq n 1u,vn) — denoting an edge between vertices u u u and v v v.

It’s guaranteed that the given edges form a tree.

The last line contains a string s s s of length n n n. The i i i-th character of s s s represents the value of vertex i i i. It’s guaranteed that s s s only contains characters 0 \mathtt{0} 0, 1 \mathtt{1} 1 and ? \mathtt{?} ?.

It is guaranteed that the sum of n n n over all test cases doesn’t exceed 2 ⋅ 1 0 5 2\cdot 10^5 2105.

Output

For each test case, output a single integer — the final score of the tree.

Example

input
6
4
1 2
1 3
4 1
0101
4
1 2
3 2
2 4
???0
5
1 2
1 3
2 4
2 5
?1?01
6
1 2
2 3
3 4
5 3
3 6
?0???
5
1 2
1 3
1 4
1 5
11?1?
2
2 1
??
output
2
1
1
2
1
0

Note

In the first test case, all the values of the vertices have been determined. There are three different paths from the root to a leaf:

  • From vertex 1 1 1 to vertex 2 2 2. The string formed by the path is 01 \mathtt{01} 01, so the weight of the leaf is 0 − 1 = − 1 0-1=-1 01=1.
  • From vertex 1 1 1 to vertex 3 3 3. The string formed by the path is 00 \mathtt{00} 00, so the weight of the leaf is 0 − 0 = 0 0-0=0 00=0.
  • From vertex 1 1 1 to vertex 4 4 4. The string formed by the path is 01 \mathtt{01} 01, so the weight of the leaf is 0 − 1 = − 1 0-1=-1 01=1.

Thus, there are two leaves with non-zero weight, so the score of the tree is 2 2 2.

In the second test case, one of the sequences of optimal choices for the two players can be:

  • Iris chooses to change the value of the vertex 3 3 3 to 1 \mathtt 1 1.
  • Dora chooses to change the value of the vertex 1 1 1 to 0 \mathtt 0 0.
  • Iris chooses to change the value of the vertex 2 2 2 to 0 \mathtt 0 0.

The final tree is as follows:
Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解,在这里插入图片描述,第2张

The only leaf with non-zero weight is 3 3 3, so the score of the tree is 1 1 1. Note that this may not be the only sequence of optimal choices for Iris and Dora.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const long double eps = 1e-8;

void solve() {
	int n;
	cin >> n;
	std::vector<int> a(n + 1, 0);
	for (int i = 1; i <= n; i ++) cin >> a[i];

	int res = 0, lst = 0;
	for (int i = 2; i <= n; i ++) {
		if (a[i - 1] == 1) continue;
		int j = floor(log2((long double)log(a[i]) * 1.0 / log(a[i - 1])));
		if (j >= lst) { lst = 0; continue; }
		if (a[i] == 1) {
			cout << -1 << endl;
			return;
		}
		int k = ceil((long double)lst * 1.0 - log2(log(a[i]) * 1.0 / log(a[i - 1])));
		res += k, lst = k;
	}
	cout << res << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

E. Iris and the Tree

Problem Statement

Given a rooted tree with the root at vertex 1 1 1. For any vertex i i i ( 1 < i ≤ n 1 < i \leq n 1<in) in the tree, there is an edge connecting vertices i i i and p i p_i pi ( 1 ≤ p i < i 1 \leq p_i < i 1pi<i), with a weight equal to t i t_i ti.

Iris does not know the values of t i t_i ti, but she knows that ∑ i = 2 n t i = w \displaystyle\sum_{i=2}^n t_i = w i=2nti=w and each of the t i t_i ti is a non-negative integer.

The vertices of the tree are numbered in a special way: the numbers of the vertices in each subtree are consecutive integers. In other words, the vertices of the tree are numbered in the order of a depth-first search.
Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解,在这里插入图片描述,第3张

The tree in this picture satisfies the condition. For example, in the subtree of vertex 2 2 2, the vertex numbers are 2 , 3 , 4 , 5 2, 3, 4, 5 2,3,4,5, which are consecutive integers.
Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解,在这里插入图片描述,第4张

The tree in this picture does not satisfy the condition, as in the subtree of vertex 2 2 2, the vertex numbers 2 2 2 and 4 4 4 are not consecutive integers.

We define dist ⁡ ( u , v ) \operatorname{dist}(u, v) dist(u,v) as the length of the simple path between vertices u u u and v v v in the tree.

Next, there will be n − 1 n - 1 n1 events:

  • Iris is given integers x x x and y y y, indicating that t x = y t_x = y tx=y.

After each event, Iris wants to know the maximum possible value of dist ⁡ ( i , i   m o d   n + 1 ) \operatorname{dist}(i, i \bmod n + 1) dist(i,imodn+1) independently for each i i i ( 1 ≤ i ≤ n 1\le i\le n 1in). She only needs to know the sum of these n n n values. Please help Iris quickly get the answers.

Note that when calculating the maximum possible values of dist ⁡ ( i , i   m o d   n + 1 ) \operatorname{dist}(i, i \bmod n + 1) dist(i,imodn+1) and dist ⁡ ( j , j   m o d   n + 1 ) \operatorname{dist}(j, j \bmod n + 1) dist(j,jmodn+1) for i ≠ j i \ne j i=j, the unknown edge weights may be different.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1t104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n n n and w w w ( 2 ≤ n ≤ 2 ⋅ 1 0 5 2 \le n \le 2 \cdot 10^5 2n2105, 0 ≤ w ≤ 1 0 12 0 \leq w \leq 10^{12} 0w1012) — the number of vertices in the tree and the sum of the edge weights.

The second line of each test case contains n − 1 n - 1 n1 integers p 2 , p 3 , … , p n p_2, p_3, \ldots, p_n p2,p3,,pn ( 1 ≤ p i < i 1 \leq p_i < i 1pi<i) — the description of the edges of the tree.

Then follow n − 1 n-1 n1 lines indicating the events. Each line contains two integers x x x and y y y ( 2 ≤ x ≤ n 2 \leq x \leq n 2xn, 0 ≤ y ≤ w 0 \leq y \leq w 0yw), indicating that t x = y t_x = y tx=y.

It is guaranteed that all x x x in the events are distinct. It is also guaranteed that the sum of all y y y equals w w w.

It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105.

Output

For each test case, output one line containing n − 1 n-1 n1 integers, each representing the answer after each event.

Example

input
4
2 1000000000000
1
2 1000000000000
4 9
1 1 1
2 2
4 4
3 3
6 100
1 2 3 2 1
6 17
3 32
2 4
4 26
5 21
10 511
1 2 2 4 2 1 1 8 8
3 2
6 16
10 256
9 128
2 1
5 8
8 64
4 4
7 32
output
2000000000000
25 18 18
449 302 247 200 200
4585 4473 2681 1567 1454 1322 1094 1022 1022

Note

In the first test case, dist ⁡ ( 1 , 2 ) = dist ⁡ ( 2 , 1 ) = t 2 = w = 1 0 12 \operatorname{dist}(1, 2) = \operatorname{dist}(2, 1) = t_2 = w = 10^{12} dist(1,2)=dist(2,1)=t2=w=1012, so dist ⁡ ( 1 , 2 ) + dist ⁡ ( 2 , 1 ) = 2 ⋅ 1 0 12 \operatorname{dist}(1, 2) + \operatorname{dist}(2, 1) = 2 \cdot 10^{12} dist(1,2)+dist(2,1)=21012.

In the second test case, the tree after Iris found out all t x t_x tx is shown below:
Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解,在这里插入图片描述,第5张

dist ⁡ ( 1 , 2 ) = t 2 \operatorname{dist}(1, 2) = t_2 dist(1,2)=t2, dist ⁡ ( 2 , 3 ) = t 2 + t 3 \operatorname{dist}(2, 3) = t_2 + t_3 dist(2,3)=t2+t3, dist ⁡ ( 3 , 4 ) = t 3 + t 4 \operatorname{dist}(3, 4) = t_3 + t_4 dist(3,4)=t3+t4, dist ⁡ ( 4 , 1 ) = t 4 \operatorname{dist}(4, 1) = t_4 dist(4,1)=t4. After the first event, she found out that t 2 = 2 t_2 = 2 t2=2, so dist ⁡ ( 1 , 2 ) = 2 \operatorname{dist}(1, 2) = 2 dist(1,2)=2. At the same time:

  • dist ⁡ ( 2 , 3 ) \operatorname{dist}(2, 3) dist(2,3) is maximized if t 3 = 7 t_3 = 7 t3=7, t 4 = 0 t_4 = 0 t4=0. Then dist ⁡ ( 2 , 3 ) = 9 \operatorname{dist}(2, 3) = 9 dist(2,3)=9.
  • dist ⁡ ( 3 , 4 ) \operatorname{dist}(3, 4) dist(3,4) and dist ⁡ ( 4 , 1 ) \operatorname{dist}(4, 1) dist(4,1) are maximized if t 3 = 0 t_3 = 0 t3=0, t 4 = 7 t_4 = 7 t4=7. Then dist ⁡ ( 3 , 4 ) = dist ⁡ ( 4 , 1 ) = 7 \operatorname{dist}(3, 4) = \operatorname{dist}(4, 1) = 7 dist(3,4)=dist(4,1)=7.

Thus, the answer is 2 + 9 + 7 + 7 = 25 2 + 9 + 7 + 7 = 25 2+9+7+7=25.

After the second event, she found out that t 4 = 4 t_4 = 4 t4=4, then t 3 = w − t 2 − t 4 = 4 t_3 = w - t_2 - t_4 = 4 t3=wt2t4=4. dist ⁡ ( 1 , 2 ) = 2 \operatorname{dist}(1, 2) = 2 dist(1,2)=2, dist ⁡ ( 2 , 3 ) = 2 + 3 = 5 \operatorname{dist}(2, 3) = 2 + 3 = 5 dist(2,3)=2+3=5, dist ⁡ ( 3 , 4 ) = 3 + 4 = 7 \operatorname{dist}(3, 4) = 3 + 4 = 7 dist(3,4)=3+4=7, dist ⁡ ( 4 , 1 ) = 4 \operatorname{dist}(4, 1) = 4 dist(4,1)=4. Thus, the answer is 2 + 5 + 7 + 4 = 18 2 + 5 + 7 + 4 = 18 2+5+7+4=18.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
 
const int N = 2e5 + 10;
 
int n, w;
std::vector<int> g[N];
int idx[N], cnt[N], dep[N], tot[N], fa[N][25];
 
void dfs(int u) {
	idx[u] = u;
	for (int i = 1; i < 25; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (auto v : g[u]) dep[v] = dep[u] + 1, dfs(v), idx[u] = max(idx[u], idx[v]);
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 24; i >= 0; i --)
		if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	if (u == v) return u;
	for (int i = 24; i >= 0; i --)
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
 
void solve() {
	cin >> n >> w;
	for (int i = 1; i <= n; i ++) g[i].clear(), idx[i] = cnt[i] = dep[i] = tot[i] = 0;
	for (int i = 2; i <= n; i ++) {
		cin >> fa[i][0];
		g[fa[i][0]].push_back(i);
	}
	dfs(1);
	for (int i = 1; i <= n; i ++)
		cnt[i] = dep[i] + dep[i % n + 1] - 2 * dep[lca(i, i % n + 1)];
 
	int res = w * n, sum = 0, st = 0;
	for (int i = 1; i < n; i ++) {
		int x, y;
		cin >> x >> y, sum += y;
		res -= (n - 2 - st) * y;
		int lst = (x + n - 1) % n;
		if (!lst) lst = n;
		// cout << idx[x] << endl;
		cnt[lst] --, cnt[idx[x]] --;
		tot[lst] += y, tot[idx[x]] += y;
		if (!cnt[lst]) res += (tot[lst] - (w - (sum - tot[lst]))), st ++;
		if (!cnt[idx[x]]) res += (tot[idx[x]] - (w - (sum - tot[idx[x]]))), st ++;//, cerr << tot[idx[x]] << endl;
		cout << res << " ";
	}
	cout << endl;
}
 
signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
 
	int dt;
	cin >> dt;
 
	while (dt --)
		solve();
 
	return 0;
}

视频讲解

Codeforces Round 969 (Div. 2)(A ~ E 题讲解)


最后祝大家早日Codeforces Round 969 (Div. 2 ABCDE题) 视频讲解,在这里插入图片描述,第6张

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!