Problem A

Part1：Problem-Solving Approach

Note that the $$$\oplus$$$ operation may either decrease an odd number by $$$1$$$ or increase an even number by $$$1$$$. The transformed operations are as follows:

1. Spend a cost of $$$x$$$ to perform $$$a \leftarrow a+1$$$.
2. Spend a cost of $$$y$$$ to perform $$$a \leftarrow a+1$$$ (if $$$a$$$ is even).
3. Spend a cost of $$$y$$$ to perform $$$a \leftarrow a-1$$$ (if $$$a$$$ is odd).

Now, we can easily categorize the original problem:

• If $$$a \gt b+1$$$: No solution.
• If $$$a = b+1$$$ and $$$b$$$ is odd: No solution.
• If $$$a = b+1$$$ and $$$b$$$ is even: The cost is $$$y$$$.
• If $$$a \leq b$$$ When $$$x$$$ is even, we can choose either operation $$$1$$$ or $$$2$$$. When $$$x$$$ is odd, we can only choose operation $$$1$$$. Since $$$a$$$ and $$$b$$$ are small, we can simulate the repeated $$$+1$$$ process.

Part2：Code Implementation

#include <bits/stdc++.h>
#define FL(i, a, b) for (int i = (a); i <= (b); ++i)
#define FR(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
int a, b, x, y;
void Solve() {
	scanf("%d %d %d %d", &a, &b, &x, &y);
	if (a > b + 1) {
		puts("-1");
	} else if (a == b + 1 && !(a & 1)) {
		puts("-1");
	} else if (a == b + 1 && (a & 1)) {
		printf("%d\n", y);
	} else {
		int ans = 0;
		for (; a < b; ++a) {
			if (a & 1) {
				ans += x;
			} else {
				ans += min(x, y);
			}
		}
		printf("%d\n", ans);
	}
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		Solve();
	}
	return 0;
}

Problem B

Part1：Problem-Solving Approach

First, the exact coordinates $$$(p_x, p_y)$$$ and $$$(q_x, q_y)$$$ don't matter — we only care about the distance between them, which we'll denote as $$$d$$$.

We can easily observe that when $$$n=2$$$, the reachable distance range is $$$[|a_1 - a_2|, a_1 + a_2]$$$.

Now let's try to generalize this to higher values of $$$n$$$. Specifically, we'll use an incremental approach to solve this. Let $$$[l, r]$$$ represent the current reachable distance interval. Suppose we've already considered the first $$$i-1$$$ operations, and now we need to move by distance $$$a_i$$$.

The upper bound $$$r$$$ is straightforward to update — we simply set $$$r \leftarrow r + a_i$$$.

For the lower bound $$$l$$$, when $$$l \leq a_i \leq r$$$, we update $$$l$$$ to $$$0$$$; Otherwise, we set $$$l \leftarrow \min(|l - a_i|, |r - a_i|)$$$. It can be easily proven by induction that this approach is optimal.

Part2：Code Implementation

#include <bits/stdc++.h>
#define FL(i, a, b) for (int i = (a); i <= (b); ++i)
#define FR(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long double ldb;
const int N = 2e5 + 10;
int n, px, py, qx, qy, a[N];
void Solve() {
	scanf("%d %d %d %d %d", &n, &px, &py, &qx, &qy);
	FL(i, 1, n) {
		scanf("%d", &a[i]);
	}
	ldb l = sqrtl(ldb(px - qx) * (px - qx) + ldb(py - qy) * (py - qy)), r = l;
	FL(i, 1, n) {
		if (l <= a[i] && a[i] <= r) {
			l = 0;
			r += a[i];
		} else {
			l = min(fabsl(l - a[i]), fabsl(r - a[i]));
			r += a[i];
		}
	}
	if (l == 0) {
		puts("Yes");
	} else {
		puts("No");
	}
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		Solve();
	}
	return 0;
}

Problem C

We start by classifying the problem based on the parity of $$$n$$$, as this is closely related to the $$$\oplus$$$ operation.

Part 1: When $$$n$$$ is odd

If $$$n$$$ is odd, we can set the answer as $$$a_1 = a_2 = \dots = a_n = l$$$.
This idea stems from the properties of $$$\oplus$$$. Specifically, if all $$$n$$$ numbers are pairwise equal, the condition will always be satisfied.

Part 2: When $$$n$$$ is even

Now, consider the case where $$$n$$$ is even. Note that in this scenario, the value of $$$a_1 \text{&} a_2 \text{&} \dots \text{&} a_n$$$ must be $$$0$$$.
The proof is straightforward—by the definition of $$$\text{&}$$$, if any binary bit is non-zero, then that bit must be $$$1$$$ for all $$$a_{1 \sim n}$$$. However, since $$$n$$$ is even, their $$$\oplus$$$ sum would be $$$0$$$, violating the problem's condition.

To summarize, the conditions we need to satisfy are:

1. $$$a_1 \text{&} a_2 \text{&} \dots \text{&} a_n = 0$$$
2. $$$a_1 \oplus a_2 \oplus \dots \oplus a_n \neq 0$$$

To ensure the lexicographically smallest answer, we aim to make the earlier elements in $$$a$$$ as small as possible.
Consider filling the first $$$n-2$$$ positions with as many $$$l$$$ values as possible, leaving the last two positions $$$a_{n-1}$$$ and $$$a_n$$$ empty. We then set $$$a_{n-1} = a_n$$$, while ensuring $$$\forall 1 \leq i \leq n-2, a_n \text{&} a_i = 0$$$.

It can be observed that a valid $$$a_n$$$ must have its highest binary bit greater than that of $$$a_1$$$, with all lower bits set to $$$0$$$.

Part 3: Code Implementation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, l, r, k;
void Solve() {
	scanf("%lld %lld %lld %lld", &n, &l, &r, &k);
	if (n & 1) {
		printf("%lld\n", l);
		return;
	}
	if (n == 2) {
		puts("-1");
		return;
	}
	if (__builtin_clzll(l) == __builtin_clzll(r)) {
		// Check if l and r have the same highest bit
		puts("-1");
		return;
	}
	ll t = 1;
	while (t <= l) {
		t <<= 1;
	}
	if (k <= n - 2) {
		printf("%lld\n", l);
		return;
	} else {
		printf("%lld\n", t);
		return;
	}
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		Solve();
	}
	return 0;
}

Problem D

Part 1: Counting Direction

Define $$$p_i$$$ as:
- The position whose mark is removed in the $$$i$$$-th operation.
- If no mark is removed, $$$p_i = 0$$$.

If we determine all values of $$$p$$$, then the number of valid $$$a$$$ sequences is the product of all $$$p_i \gt 0$$$ (since we only need $$$a_i \leq p_i$$$).
Thus, determining the $$$p$$$ array directly gives the count of corresponding $$$a$$$ sequences.

Part 2: Counting Constraints

• By definition, $$$p_i \leq i$$$ (a mark cannot be removed from the right of the operation).
• We need to decide for each mark and operation whether they match.
• Each operation must match a mark to its left.
  Therefore, at any position, the number of marks to the left must be $$$\geq$$$ the number of operations. Otherwise, some operations would have no marks to remove.

Part 3: DP Approach

We perform left-to-right DP along the number line.

Let $$$f_{i,j}$$$ ($$$j \geq 0$$$) denote:
- Among the first $$$i$$$ positions,
- There are $$$j$$$ marks still unmatched by operations.

For easier transitions, we introduce $$$g_{i,j}$$$:
- After processing marks up to position $$$i$$$ and operations up to $$$i-1$$$,
- There are $$$j$$$ unmatched marks.

Transition from $$$f_{i-1}$$$ to $$$g_i$$$ (handling mark at $$$i$$$):

1. Mark $$$i$$$ matches an operation later:
   $$$g_{i,j} \leftarrow g_{i-1,j-1} \times i$$$
   (The coefficient $$$i$$$ comes from $$$p_i$$$ choices, as explained in Part 1.)

2. Mark $$$i$$$ remains unmatched:
   $$$g_{i,j} \leftarrow f_{i-1,j}$$$

Transition from $$$g_i$$$ to $$$f_i$$$ (handling operation at $$$i$$$):

1. Operation $$$i$$$ matches a mark ($$$p_i \gt 0$$$):
   $$$f_{i,j} \leftarrow g_{i,j+1} \times (j+1)$$$
   (Here, $$$(j+1)$$$ is the number of ways to choose $$$p_i$$$.)

2. Operation $$$i$$$ does nothing ($$$p_i = 0$$$):
   $$$f_{i,j} \leftarrow g_{i,j}$$$

The final answer is $$$f_{n,0}$$$, ensuring all marks and operations are perfectly matched.

Part 3.5: Intuition

• Marks and operations resemble parentheses matching (( for marks, ) for operations).
• This is essentially a weighted variant of parenthesis counting.

Part 4: Code Implementation

#include <bits/stdc++.h>
#define FL(i, a, b) for (int i = (a); i <= (b); ++i)
#define FR(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
const int N = 5010;
int n, MOD, f[N], g[N];
void Solve() {
	scanf("%d %d", &n, &MOD);
	fill(f, f + n + 2, 0);
	f[0] = 1;
	FL(i, 1, n) {
		fill(g, g + n + 2, 0);  
		FL(j, 0, i) {
			g[j] = f[j];
			if (j) {
				g[j] = (g[j] + (ll)f[j - 1] * i) % MOD;
			}
		}
		fill(f, f + n + 2, 0);
		FL(j, 0, i) {
			f[j] = (g[j] + (ll)g[j + 1] * (j + 1)) % MOD;
		}
	}
	printf("%d\n", f[0]);
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		Solve();
	}
	return 0;
}

Problem E

Part 1: Transformation

Let the final sequence be denoted as $$$b'$$$, and let $$$c_i$$$ be the smallest number $$$\geq b_i$$$ that satisfies:

• Every bit of $$$c_i$$$ is $$$\geq$$$ the corresponding bit in $$$a_{i-1}$$$.

• Every bit of $$$c_i$$$ is $$$\geq$$$ the corresponding bit in $$$a_i$$$.

Clearly, the final $$$b'_i \geq c_i$$$. Thus, we can first set all $$$b_i \leftarrow c_i$$$ and accumulate this part of the contribution.

Part 2: Observation

Now, we only need to consider the extra bits in $$$b_i \oplus b_{i+1}$$$ compared to $$$a_i$$$.

To eliminate certain bits in $$$b_i$$$, we need to select a higher bit to flip to $$$1$$$.
Note that we will only choose one such higher bit, because keeping only the highest selected bit achieves the same effect.

Part 3: Solution Algorithm

We use dynamic programming to track the selected "higher bit."

Let $$$f_{i,j}$$$ denote the state where, for the first $$$i$$$ numbers, the $$$j$$$-th bit is chosen to flip to $$$1$$$ for the $$$i$$$-th number.
We enumerate $$$f_{i-1,k}$$$ and transition to $$$f_{i,j}$$$, ensuring that the modified $$$b_i \oplus b_{i+1} = a_i$$$.

• Special Case: For each $$$i$$$, we must allocate a separate state to represent "no additional bit flip."

The time complexity is $$$O(n \log^2 V)$$$, where $$$V$$$ is the value range.

Part 4: Code Implementation

#include <bits/stdc++.h>
#define FL(i, a, b) for (int i = (a); i <= (b); ++i)
#define FR(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const ll INF = 1e18;
int n, a[N], b[N], c[N], s[N][32];
ll f[N][32];
void Solve() {
	scanf("%d", &n);
	FL(i, 1, n - 1) {
		scanf("%d", &a[i]);
	}
	a[0] = a[n] = 0;
	FL(i, 1, n) {
		scanf("%d", &b[i]);
		ll t = a[i - 1] | a[i];
		c[i] = t | b[i];
		FR(j, 30, 0) {
			if ((c[i] >> j & 1) && !(t >> j & 1)) {
				if ((c[i] ^ (1 << j)) >= b[i]) {
					c[i] ^= (1 << j);
				}
			}
		}
		FL(j, 0, 30) {
			s[i][j] = (((c[i] >> j) | 1) << j) | t;
		}
		s[i][31] = c[i];
	}
	{
		FL(i, 0, n) {
			fill(f[i], f[i] + 32, INF);
		}
		FL(i, 0, 31) {
			if (!(b[1] >> i & 1)) {
				f[1][i] = s[1][i] - b[1];
			}
		}
		FL(i, 2, n) {
			FL(j, 0, 31) {
				if (c[i - 1] >> j & 1) {
					continue;
				}
				FL(k, 0, 31) {
					if (c[i] >> k & 1) {
						continue;
					}
					if ((s[i - 1][j] & s[i][k]) != a[i - 1]) {
						continue;
					}
					f[i][k] = min(f[i][k], f[i - 1][j] + (s[i][k] - b[i]));
				}
			}
		}
	}
	ll ans = INF;
	FL(i, 0, 31) {
		ans = min(ans, f[n][i]);
	}
	if (ans == INF) {
		puts("-1");
	} else {
		printf("%lld\n", ans);
	}
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		Solve();
	}
	return 0;
}

Problem F

Don’t be intimidated by the Div.2 F label—most F problems turn out to be simple upon analysis.

Part 1: Key Observations

We can treat $$$S$$$ as fuel, which decreases by $$$1$$$ in some places and increases by $$$1$$$ in others.

We define two adjacent nodes $$$u$$$ and $$$v$$$ with $$$w_u = w_v = 1$$$ as a gas station. Here, we can spend $$$2$$$ units of time to gain $$$2$$$ units of fuel (i.e., by moving back and forth between $$$u$$$ and $$$v$$$ once).

Part 2: Characterizing Valid Paths

It’s easy to see that if your path passes through multiple gas stations, refueling at earlier stations instead of later ones does not affect the answer. This is because your movement speed matches the lava’s spread speed.

Thus, the optimal path must consist of:

1. Traversing a path alternating between $$$1$$$ and $$$-1$$$. If two consecutive $$$-1$$$(s) appear, you die.
2. Reaching a gas station $$$(1, 1)$$$ and refueling all the fuel needed for the rest of the journey. If only step 1 is sufficient, no gas station is needed.
3. Continuing to the target node $$$U$$$.
4. Moving back and forth between $$$U$$$ and an adjacent node.

We refer to these four segments as $$$path_{1 \sim 4}$$$.

Part 3: Maintaining Such Paths

For $$$path_{1 \sim 2}$$$, we can use the BFS algorithm to preprocess, for each node $$$u$$$, the nearest gas station $$$rd_u$$$ reachable via $$$path_1$$$.

For $$$path_3$$$, we can start from the initial node $$$st$$$ and search for all possible $$$U$$$, computing the corresponding contributions.

Specifically, during the search, we track:

• The distance $$$d$$$ from $$$st$$$ to $$$U$$$.
• The maximum fuel deficit $$$need$$$ encountered while moving from $$$st$$$ to $$$U$$$.
  This determines how much fuel we need to refuel at the gas station.
• The distance $$$rec\text{_}dis$$$ to the nearest gas station.

When reaching a node $$$U$$$, we can easily compute the total time required under the optimal strategy and compare it with the lava submergence time at $$$U$$$.

If $$$U$$$ is reachable, the total length of $$$path_{1 \sim 4}$$$ is either $$$\text{dist}(1, U)$$$ or $$$\text{dist}(1, U) - 1$$$. By induction, we take $$$\text{dist}(1, U) - 1$$$ if and only if $$$\text{dist}(1, st)$$$ is odd.

Part 4: Code Implementation

#include <bits/stdc++.h>
#define FL(i, a, b) for (int i = (a); i <= (b); ++i)
#define FR(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
const int N = 5e5 + 10, INF = 1e9;
int n, st, ans, w[N], rd[N], dep[N];
vector<int> G[N];
void Dfs1(int u, int fa) {
	for (int v: G[u]) {
		if (v != fa) {
			dep[v] = dep[u] + 1;
			Dfs1(v, u);
		}
	}
}
void CalcRecent() {
	queue<int> que;
	fill(rd, rd + n + 1, INF);
	FL(u, 1, n) for (int v: G[u]) {
		if (w[u] == 1 && w[v] == 1) {
			rd[u] = 0, que.emplace(u);
			break;
		}
	}
	while (!que.empty()) {
		int u = que.front();
		que.pop();
		for (int v: G[u]) {
			if (w[v] != w[u] && rd[v] == INF) {
				rd[v] = rd[u] + 1;
				que.emplace(v);
			}
		}
	}
}
void Dfs2(int u, int fa, int d, int s, int need, int rec_d) {
	if (!(need = max(need, -s))) {
		rec_d = min(rec_d, rd[u]);
	}
	int t = ((need + 1) / 2 + rec_d) * 2;
	if (d + (need? t : 0) < dep[u]) {
		ans = max(ans, dep[u] - (dep[st] % 2 == 0));
	}
	for (int v: G[u]) {
		if (v != fa) {
			Dfs2(v, u, d + 1, s + w[v], need, rec_d);
		}
	}
}
void Solve() {
	scanf("%d %d", &n, &st);
	FL(i, 1, n) {
		scanf("%d", &w[i]);
		G[i].clear();
	}
	FL(i, 1, n - 1) {
		int u, v;
		scanf("%d %d", &u, &v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	Dfs1(1, 0);
	CalcRecent();

	ans = 0;
	Dfs2(st, 0, 0, w[st], 0, INF);
	printf("%d\n", ans);
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		Solve();
	}
	return 0;
}