You are allowed to use intermediate vertices in your sequence. Does it ever actually help? For any three vertices $$$a$$$, $$$b$$$, $$$c$$$, what is the relationship between $$$c(a,b) + c(b,c)$$$ and $$$c(a,c)$$$? Recall that for non-negative integers, $$$x + y \geq x \oplus y$$$.

Since, $$$c(a,b) + c(b,c) \geq c(a,b) \oplus c(b,c)$$$, Splitting the path doesn't minimize the distance at all. Hence $$$d(u,v) = c(u,v)$$$ always.

Since $$$d(u,v) = c(u,v)$$$ always, we can maintain a running mask $$$M$$$ (XOR of all Type 1 updates so far). A path with $$$\ell$$$ edges has its XOR-distance changed only if $$$\ell$$$ is odd, flipping their XOR-distance by $$$M$$$, depending only on the running XOR of Type 1 queries so far. Can you precompute something per vertex that makes answering queries $$$O(log(w))$$$?

Observation 1: Intermediate jumps never help.

For any three vertices $$$a$$$, $$$b$$$, $$$c$$$:

since $$$x + y \geq x \oplus y$$$ for all non-negative integers. Therefore any intermediate vertex only increases the total cost, so $$$d(u,v) = c(u,v)$$$ always.

Observation 2: Effect of the running mask.

Maintain a running mask $$$M$$$ (of Type 1 queries), updated in $$$O(1)$$$ per type-1 query. A path with $$$\ell$$$ edges has its XOR-distance changed only if $$$\ell$$$ is odd, flipping their XOR-distance by exactly $$$M$$$.

Precomputation.

For each vertex $$$s$$$ and each bit $$$b$$$, store four counts using rerooting DP in $$$O(nlog(w))$$$:

• $$$even[s][b][0/1]$$$ = # vertices reachable from $$$s$$$ via an even-length path with bit $$$b$$$ of XOR-distance $$$= 0$$$ or $$$1$$$
• $$$odd[s][b][0/1]$$$ = same but for odd-length paths

When merging a child $$$v$$$ into $$$u$$$ via an edge of weight $$$w$$$, extending any path from $$$v$$$ through this edge to $$$u$$$ does two things: the path length parity flips (odd $$$\leftrightarrow$$$ even), and the XOR-distance gets XOR'd with $$$w$$$, so if bit $$$b$$$ of $$$w$$$ is $$$1$$$ the bit flips, otherwise it stays.

If bit $$$b$$$ of $$$w$$$ is $$$1$$$:

Similar Transitions occur if bit $$$b$$$ of $$$w$$$ is $$$0$$$

We can use a standard DFS pass to build up these values over the subtrees. And a rerooting pass to add the upward contribution using the same transitions.

For $$$type-1$$$ queries we can maintain a running XOR of the previous $$$type-1$$$ updates

For $$$type-2$$$ queries:

For each bit $$$b$$$:

• Even-length path vertices are unaffected by $$$M$$$ $$$\to$$$ contribute $$$even[s][b][1]$$$ vertices with bit $$$b$$$ set.
• Odd-length path vertices have bit $$$b$$$ of their distance flipped iff bit $$$b$$$ of $$$M$$$ is $$$1$$$ $$$\to$$$ contribute $$$odd[s][b][0]$$$, else $$$odd[s][b][1]$$$.

The answer is $$$\displaystyle\sum_{b=0}^{29} 2^b \cdot cnt_b$$$, computed in $$$O(log(w))$$$.

Complexity: $$$O(nlog(w))$$$ precomputation, $$$O(1)$$$ per type-1 query, $$$O(log(w))$$$ per type-2 query.

For small values of $$$n$$$, $$$1$$$ is a trivial base case, but $$$2$$$ and $$$3$$$ are impossible because the difference $$$1$$$ is not prime. Try to find a valid sequence for $$$n = 5$$$ that is lexicographically smallest.

To keep the sequence lexicographically small, we naturally want to start with $$$1$$$. The smallest prime jump we can make is $$$2$$$. This gives us $$$1, 3, 5$$$. To fill in the missing numbers without getting stuck, we can jump $$$5 \to 2 \to 4$$$, forming the block: 1 3 5 2 4.

Notice that the next number can be $$$6$$$ (since $$$|4 - 6| = 2$$$), which starts the next shifted block of $$$5$$$: 6 8 10 7 9. How can you handle the remaining elements when $$$n$$$ is not a multiple of $$$5$$$?

Observations: We are asked to find the lexicographically smallest sequence where the absolute difference between any two adjacent elements is prime.

• For $$$n = 1$$$, the answer is just 1.
• For $$$n = 2$$$ and $$$n = 3$$$, it's impossible to form a valid sequence because the elements are too close to each other, and the number $$$1$$$ is not prime.
• For $$$n = 4$$$, the smallest valid configuration requires us to start with 2 because starting with 1 eventually forces a difference of $$$1$$$ or leaves no valid jumps. The sequence is 2 4 1 3.

Building Blocks of 5: For $$$n \ge 5$$$, to ensure the sequence is lexicographically smallest, we should ideally start with $$$1$$$ and increment by the smallest prime, which is $$$2$$$. This gives the prefix $$$1, 3, 5$$$. From $$$5$$$, we can jump back to $$$2$$$ (difference of $$$3$$$), and from $$$2$$$ to $$$4$$$ (difference of $$$2$$$).

This gives us a perfectly self-contained block of $$$5$$$ elements: $$$1, 3, 5, 2, 4$$$.
If we shift this pattern by $$$5$$$, the next block is $$$6, 8, 10, 7, 9$$$. The transition between blocks is valid because the difference between the end of the first block ($$$4$$$) and the start of the second block ($$$6$$$) is $$$2$$$, which is prime. Thus, we can safely build the array in chunks of $$$5$$$.

Handling Remainders (How we found the suffixes): If $$$n$$$ is not perfectly divisible by $$$5$$$, we need to adjust the last few elements. But how do we know exactly which numbers to place there?

The key insight is that prime differences are translation-invariant (i.e., $$$(a+x) - (b+x) = a - b$$$). Because the number of elements we need to "fix" is very small (between $$$1$$$ and $$$4$$$ elements), we can simply write a quick brute-force script using next_permutation to find the lexicographically smallest valid arrays for $$$n=6, 7, 8,$$$ and $$$9$$$.

Once we observe the optimal endings for those small cases, we can express those last few numbers algebraically in terms of $$$n$$$. This allows us to safely overwrite the trailing elements of our generated sequence:

1. $$$n \pmod 5 = 1$$$: The sequence is already perfectly valid if we just append $$$n$$$. The last element of the complete block is $$$n-2$$$, and $$$|n - (n-2)| = 2$$$ (prime).
2. $$$n \pmod 5 = 2$$$: We overwrite the last $$$3$$$ elements. To maintain valid prime jumps from the previous block and use up the remaining numbers optimally, the pattern generalizes to ending with $$$n, n-3, n-1$$$.
3. $$$n \pmod 5 = 3$$$: We overwrite the last $$$4$$$ elements. The algebraically derived pattern for this remainder is $$$n-1, n-4, n-2, n$$$.
4. $$$n \pmod 5 = 4$$$: We overwrite the last $$$4$$$ elements. The pattern ends with $$$n-2, n, n-3, n-1$$$. Notice that if we plug in $$$n=4$$$, this perfectly yields the base case sequence 2 4 1 3.

Time Complexity: We iterate through the array to place elements, which takes $$$O(1)$$$ operations per index. Thus, the time complexity per testcase is $$$O(n)$$$. Over all testcases, the total time complexity is $$$O(\sum n)$$$, which easily fits within the $$$1$$$ second time limit.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1;
        return;
    } else if (n <= 3) {
        cout << -1;
        return;
    }

    vector<int> ans(n + 1);

    for (int i = 1; i + 4 <= n; i += 5) {
        ans[i] = i;
        ans[i + 1] = i + 2;
        ans[i + 2] = i + 4;
        ans[i + 3] = i + 1;
        ans[i + 4] = i + 3;
    }

    if (n % 5 == 1) {
        ans[n] = n;
    } else if (n % 5 == 2) {
        ans[n] = n - 1;
        ans[n - 1] = n - 3;
        ans[n - 2] = n;
    } else if (n % 5 == 3) {
        ans[n] = n;
        ans[n - 1] = n - 2;
        ans[n - 2] = n - 4;
        ans[n - 3] = n - 1;
    } else if (n % 5 == 4) {
        ans[n] = n - 1;
        ans[n - 1] = n - 3;
        ans[n - 2] = n;
        ans[n - 3] = n - 2;
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
}

Note that in each move, a player must choose a maximal block comprising the same element.

If all the elements are distinct, the answer will be independent of the rearrangement. What happens if there is at least one duplicate?

Note that in each move, a player must choose a maximal block comprising the same element.

If all the elements are distinct, the answer will be independent of the rearrangement. If $$$n$$$ is odd, Alice wins, and if $$$n$$$ is even, Bob wins.

Otherwise, there is at least one duplicate. Let the distinct elements in the array be $$$x_1, x_2, \ldots, x_m$$$ and let $$$X_i$$$ denote a block of $$$x_i$$$s. For simplicity, let's assume $$$x_1$$$ occurs at least $$$2$$$ times in the array $$$a$$$. Now, Alice can always guarantee a win with the following strategy:

• $$$m$$$ is odd: Rearrange the array to $$$[X_1, X_2, \ldots, X_m]$$$ and remove any block on her first move.
• $$$m$$$ is even: Rearrange the array to $$$[X_1, X_2, \ldots, X_m, X_1]$$$ and remove the last block on her first move.

Thus, Bob can win if and only if $$$n$$$ is even and all the elements are distinct.

What happens if $$$a_{i+1}=1$$$?

If $$$a_2, a_3, \dots, a_n \ge 2$$$, what does $$$a_i \bmod a_{i+1}=1$$$ tell us about the relationship between adjacent elements in this suffix?

Since any integer modulo 1 is 0, $$$a_{i+1}$$$ can never be 1. Thus, elements $$$a_2$$$ through $$$a_n$$$ must be at least 2. For any integers $$$x, y \ge 2$$$, $$$x \bmod y=1$$$ implies $$$x \gt y$$$. Thus, the subarray $$$a_2, \dots, a_n$$$ must be strictly decreasing. Hence, the final sequence is $$$1, n, n-1, \dots, 2$$$.

#include<bits/stdc++.h>

using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    cout << 1 << " ";
    while (n > 1) {
      cout << n << " ";
      --n;
    }
    cout << endl;
  }
}

The problem can be modeled into a directed graph, draw out some valid graphs for small n, what kind of graphs are these?

If you know answer for $$$i - 1$$$ players, can you relate it to find answer for $$$i$$$ players?

Lets reword the problem first. The problem essentially boils down to the following statement:

You have a directed graph consisting of $$$n$$$ nodes, where every node has an out-degree of $$$1$$$ and except one node every other node has in-degree $$$ \gt 0$$$. There are no self-loops in the graph. We have to count total number of such graphs.

From the above observations, the graph splits into $$$X$$$ $$$(X \ge 1)$$$ disjoint components. Among these, $$$X - 1$$$ components are simple cycles, while the remaining component contains a cycle along with a tail that eventually merges into a node within that component.

To help you visualize this, for $$$X = 2$$$ one such example is following:

Let $$$f(n)$$$ denote the total valid graphs for given $$$n$$$ nodes. Lets call the node with no ingoing edge as bad node.

Lets say there's some valid graph for $$$n-1$$$ nodes we can add one additional node and if the outgoing edge of it points towards the existing bad node, the new resulting graph contributes to $$$f(n)$$$.

Since we can choose any of the $$$n$$$ nodes as the new bad node:

$$$f(n) \supset n \cdot f(n - 1)$$$

But this alone is not it, there's one more case wherein the $$$n - 1$$$ nodes forms a set of disjoint directed cycles and the bad node points to any of the remaining $$$n - 1$$$ nodes.

Visually the following depicts this case:

As you can see, the bad node can point to any of other $$$n - 1$$$ nodes and the resulting graph would be valid.

There are $$$n$$$ ways to choose the bad node, $$$n - 1$$$ ways to choose the node to which it points, lets say the total number of ways to form a set of disjoint cyclic graph from $$$n - 1$$$ nodes be $$$d(n - 1)$$$.

So in overall,

$$$f(n) = n * f(n - 1) + n * (n - 1) * d(n - 1)$$$

We only need to find $$$d(n - 1)$$$ or say $$$d(n)$$$.

To find $$$d(n)$$$, let us consider one example of disjoint cyclic graph formed using n nodes, since each of $$$n$$$ node has exactly 1 ingoing edge, we will depict the graph with the help of an array $$$A$$$ of size $$$n$$$ such that there's an edge from $$$A[i]$$$ to $$$i$$$.

Since there are no self loops in this graph, $$$A[i] \ne i$$$,

With the above condition in mind, $$$d(n)$$$ = total number of permutation of $$$A = [1, 2, 3, \dots, n]$$$ such that $$$A[i] \ne i$$$.

The above is also known as derangement of $$$n$$$.

Lets say $$$A[i] = 1$$$ for some $$$1 \lt i \le n$$$. Now the element $$$i$$$ in the permutation has two choices:

1. Go to position $$$1$$$

2. Go to position other than $$$1$$$

In the first case, we have essentially swapped out places for element $$$1$$$ and element $$$i$$$ in the sorted permutation and the remaining $$$n - 2$$$ elements have to ensure to re-arrange themselves such that $$$A[j] \ne j$$$, this is nothing but $$$d(n - 2)$$$.

In the second case, we have two restrictions, $$$A[j] \ne j$$$ and $$$A[1] \ne i$$$, since for each value $$$ \gt 1$$$, we have exactly one distinct restricted index, this is nothing but $$$d(n - 1)$$$.

Since we can choose the index $$$i$$$ in $$$n - 1$$$ ways,

$$$d(n) = (n - 1) * (d(n - 1) + d(n - 2))$$$

So we have finally arrived at two recursive relations

$$$d(n) = (n - 1) * (d(n - 1) + d(n - 2))$$$

with the base case being $$$d(1) = 0$$$, $$$d(2) = 1$$$.

and

$$$f(n) = n * f(n - 1) + n * (n - 1) * d(n - 1)$$$, for $$$n \gt 2$$$

with the base case being $$$f(2) = 0$$$.

Since $$$N \le 10^6$$$, you can precompute $$$f(n)$$$ as well as $$$d(n)$$$ in linear time and just output $$$f(n)$$$ for the input $$$n$$$.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 1e6 + 69;
vector<ll> f(N), d(N);
 
const int MOD = 998244353;
 
void precompute() {
    d[1] = 0;
    d[2] = 1;
 
    for(ll i = 3; i < N; i++) {
        f[i] = ((f[i - 1] * i) % MOD + (((i * (i - 1)) % MOD) * d[i - 1]) % MOD) % MOD;
        d[i] = ((i - 1) * (d[i - 1] + d[i - 2]) % MOD);
    }
}
 
void solution(){
    int n;
    cin >> n;
    cout << f[n] << endl;    
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
#ifdef PenguinsAreCool
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("debug.txt","w",stderr);
#endif
    precompute();
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        solution();
    }
}

Who wins when all elements of $$$a$$$ are equal?

Who wins when $$$a = [1, 1, 1, \dots, 1, x]$$$ where $$$x \gt 1$$$?

How can this configuration be forced during the game?

Let $$$g = \gcd(a_1, a_2, \dots, a_n)$$$.

Observe that dividing all elements by $$$g$$$ does not affect the game, since all gcd relations are preserved up to scaling. Hence, without loss of generality, we may assume $$$\gcd(a_1, a_2, \dots, a_n) = 1$$$.

Case 1: All elements are equal to $$$1$$$.

In this case, no valid move exists, since for any subsequence, all elements are equal to its gcd. Hence, Alice cannot make a move and therefore wins.

Case 2: The array is of the form $$$a = [1, 1, \dots, 1, x]$$$ where $$$x \gt 1$$$.

Any valid move must include the element $$$x$$$, since otherwise the subsequence consists only of $$$1$$$s and is invalid. If $$$x$$$ is included, the gcd of the chosen subsequence is $$$1$$$, and all selected elements become $$$1$$$. Thus, after one move, the array becomes identically $$$1$$$.

Therefore, the player making this move leaves no valid moves for the opponent. Hence, Alice loses and Bob wins.

Case 3: $$$n = 2$$$ and the array is not covered by the above cases.

Since $$$\gcd(a_1, a_2) = 1$$$, the only valid move is to select both elements, after which the array becomes $$$[1,1]$$$. This reduces the game to Case 1, so Bob wins.

Case 4: All remaining cases.

Consider all subsequences of size $$$n-1$$$. We claim that if there exists at least one such subsequence with gcd equal to $$$1$$$, then Alice wins; otherwise, Bob wins.

Conclusion:

• If all elements are $$$1$$$, Alice wins.
• Else if the array is of the form $$$[1, 1, \dots, 1, x]$$$, Bob wins.
• Else if $$$n = 2$$$, Bob wins.
• Otherwise, check if there exists a subsequence of size $$$n-1$$$ with gcd $$$1$$$:
• If yes, Alice wins.
• Otherwise, Bob wins.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
 
void solve() {
    ll n;
    cin >> n;

    vector<ll> a(n);
    for (ll i=0; i<n; i++) cin >> a[i];
    ll g = 0;
    for (ll i=0; i<n; i++) {
        g = gcd(g, a[i]);
    }

    for (ll i=0; i<n; i++) a[i] /= g;

    if (n == 2) {
        if (a[0] == a[1]) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }

        return;
    }

    ll one_cnt = 0;;
    for (ll i=0; i<n; i++) if (a[i] == 1) one_cnt++;

    if (one_cnt == n) {
        cout << "Alice" << endl;
        return;
    } else if (one_cnt == n-1) {
        cout << "Bob" << endl;
        return;
    }

    vector<ll> gcd_pref(n+2);
    vector<ll> gcd_suf(n+2);
    
    for (ll i=0; i<n; i++) {
        gcd_pref[i+1] = gcd(gcd_pref[i], a[i]);
    }
    for (ll i=n-1; i>=0; i--) {
        gcd_suf[i+1] = gcd(gcd_suf[i+2], a[i]);
    }

    for (ll i=1; i<=n; i++) {
        if (gcd(gcd_pref[i-1], gcd_suf[i+1]) == 1) {
            cout << "Alice" << endl;
            return;
        }
    }

    cout << "Bob" << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;

    while (t--) solve();
    
    return 0;
}

How can we efficiently determine whether we can travel from any shelter a to shelter b?

Think in terms of DSU (Disjoint Set Union).

Consider an array $$$nearestShelter$$$, where $$$nearestShelter[i]$$$ denotes the nearest shelter to node $$$i$$$.

Now observe that we can travel from shelter $$$a$$$ to shelter $$$b$$$ if and only if there exists a node $$$x$$$ such that both shelters $$$a$$$ and $$$b$$$ can reach $$$nearestShelter[x]$$$ with total distance $$$\le k$$$.

To compute this efficiently, perform a multisource Dijkstra with all shelters as initial sources.

While running Dijkstra, we also maintain DSU components to group nodes/shelters.

Suppose we are currently processing node $$$x$$$ in Dijkstra:

Case 1 — $$$x$$$ is visited for the first time

• Store the minimum distance $$$dist[x]$$$
• Assign $$$x$$$ to the same component as its parent (the node from which we reached $$$x$$$)
• Push all neighbours $$$v$$$ such that:

Case 2 — $$$x$$$ is already visited
Let:

• current distance = $$$d$$$
• minimum recorded distance = $$$minD$$$

Check:

• If true → merge the two components:
• the component of $$$x$$$
• the component from which we arrived

• Otherwise → do nothing

We can do this because if two paths from different shelters meet at $$$x$$$ with total distance $$$\le k$$$, then those shelters are mutually reachable within the limit.

Final Answer: Nodes $$$a$$$ and $$$b$$$ are reachable if and only if they belong to the same DSU component with treating initial node also as shelter(because there also your total travel time initially is 0).

Time Complexity:
Same as Dijkstra + DSU:

Before diving into the solution, let's define the terms and algorithms we will use:

Variables & Notation:

• $$$n$$$: The number of vertices in the tree.
• $$$a_i$$$: The weight array given in the input, used to calculate probabilities.
• $$$c_i$$$: The cost array given in the input, used to calculate the final sum.
• $$$S_k$$$: The prefix sum of the array $$$a$$$. Specifically, $$$S_k = \sum_{j=1}^k a_j$$$.
• $$$F$$$: The random variable representing the sum of $$$c_i$$$ for all leaf vertices.
• $$$P_i$$$: The probability that vertex $$$i$$$ ends up as a leaf in the final tree.

Algorithmic Concepts:

• Linearity of Expectation: A probability rule stating that the expected value of a sum is the sum of the expected values ($$$E[A + B] = E[A] + E[B]$$$). We use this to look at each vertex individually.
• NTT (Number Theoretic Transform): A fast algorithm used to multiply two polynomials of degree $$$N$$$ in $$$\mathcal{O}(N \log N)$$$ time, designed to work with large modulo arithmetic (like 998244353).
• Polynomial Remainder Theorem: A theorem stating that the remainder of dividing a polynomial $$$P(x)$$$ by $$$(x - c)$$$ is exactly $$$P(c)$$$. We use Newton's Method to compute these polynomial remainders (modulo operations) quickly.

Use Linearity of Expectation. Instead of trying to find the expected total sum $$$F$$$ directly, consider each vertex independently. The expected sum can be written as:

Now, the problem reduces to finding $$$P_i$$$, the probability that vertex $$$i$$$ is a leaf in the final tree.

When is vertex $$$i$$$ a leaf?

By the problem definition, a vertex is a leaf if it is not the root (vertex $$$1$$$ is never a leaf) and its degree is $$$1$$$. Because vertex $$$i$$$ connects to exactly one vertex $$$j \lt i$$$ when it is added, its degree starts at $$$1$$$. It will only remain $$$1$$$ if no subsequent vertex $$$k \gt i$$$ chooses to connect to $$$i$$$.

Since the choice of parent for each vertex is independent, the probability $$$P_i$$$ is the product of the probabilities that each subsequent vertex $$$k \in [i+1, n]$$$ does not connect to $$$i$$$.

Recall our definition of $$$S_k = \sum_{j=1}^k a_j$$$.

When vertex $$$k$$$ is added, it chooses its parent from vertices $$$1$$$ to $$$k-1$$$. The probability that vertex $$$k$$$ connects specifically to vertex $$$i$$$ is $$$\frac{a_i}{S_{k-1}}$$$.

Therefore, the probability that vertex $$$k$$$ does not connect to $$$i$$$ is $$$\left(1 - \frac{a_i}{S_{k-1}}\right)$$$.

For a given vertex $$$i$$$, the overall probability $$$P_i$$$ is exactly:

Notice that $$$P_i$$$ looks like the evaluation of a polynomial. Specifically, if we define a polynomial $$$f_i(x) = \prod_{k=i+1}^n \left(1 - \frac{x}{S_{k-1}}\right)$$$, then $$$P_i = f_i(a_i)$$$.

Calculating $$$f_i(a_i)$$$ naively for all $$$i$$$ takes $$$\mathcal{O}(n^2)$$$ time, which is too slow.

However, $$$f_i(x)$$$ is just a suffix product of linear polynomials. If we reverse the sequence of operations, this becomes a prefix product. We can use a Divide and Conquer approach combined with Fast Multipoint Evaluation to evaluate all $$$P_i$$$ in $$$\mathcal{O}(n \log^2 n)$$$ time.

Mathematical Formulation

As established in the hints, by linearity of expectation, our answer is $$$\sum_{i=1}^n c_i \cdot P_i$$$.

• For vertex $$$1$$$ (the root), $$$P_1 = 0$$$ by definition. Our formula elegantly handles this because $$$1 - \frac{a_1}{S_1} = 0$$$.
• For vertex $$$n$$$, no vertices are added after it, so $$$P_n = 1$$$.
• For $$$1 \lt i \lt n$$$, we must compute:

Array Reversal: Suffix to Prefix

To compute this efficiently, we want to evaluate a sequence of polynomials at given points. Notice that our formula for $$$P_i$$$ requires multiplying terms from $$$i+1$$$ up to $$$n$$$ (a suffix product).

By reversing the $$$a$$$ array and the prefix sum array ($$$S$$$), we elegantly transform this "forward-looking" suffix product into a "backward-looking" prefix product. This allows our Divide and Conquer algorithm to process the polynomials sequentially from left to right. (After computing the probabilities, we simply reverse the answers back to their original order).

Divide and Conquer with Polynomials

Instead of calculating everything at once, we use a Divide and Conquer approach. For any recursive range $$$[l, r]$$$, we define and precompute two polynomials bottom-up:

1. $$$Poly_1$$$ (The Probability Polynomial): $$$Poly_1(l, r) = \prod_{k=l}^r \left(1 - \frac{x}{S_{k-1}}\right)$$$
2. $$$Poly_2$$$ (The Modulo Polynomial): $$$Poly_2(l, r) = \prod_{k=l}^r (x - a_k)$$$

By combining adjacent ranges (multiplying their polynomials using NTT), we can build these for all ranges $$$[l, r]$$$ in the recursion tree in $$$\mathcal{O}(n \log^2 n)$$$ time.

The Modulo Magic (Fast Multipoint Evaluation)

To find the answers, we run a recursive function evaluate(l, r, cur) top-down, starting with evaluate(1, n, 1). As we divide the range $$$[l, r]$$$ into left $$$[l, mid]$$$ and right $$$[mid+1, r]$$$ halves, we must update and pass down our current polynomial cur.

If we just kept multiplying terms, the degree of cur would quickly grow to $$$n$$$, making operations at every step $$$\mathcal{O}(n \log n)$$$ and leading to an $$$\mathcal{O}(n^2 \log n)$$$ Time Limit Exceeded (TLE).

To prevent this, we use the Polynomial Remainder Theorem and Fast Multipoint Evaluation. The mathematical insight is that evaluating a large polynomial $$$P(x)$$$ at a set of points is exactly the same as evaluating its remainder when divided by the product of $$$(x - x_i)$$$ for those points.

Our polynomial $$$Poly_2(l, r)$$$ represents exactly this product for the current range. By continuously replacing cur with cur $$$\pmod{Poly_2(l, r)}$$$, we guarantee that the degree of cur is always strictly bounded by $$$r - l + 1$$$.

Here is how we branch our recursion from $$$[l, r]$$$:

1. Going Left [l, mid]: We simply take the remainder of cur against the left half's roots. cur_left $$$=$$$ cur $$$\pmod{Poly_2(l, mid)}$$$
2. Going Right [mid+1, r]: We must include the probabilities accumulated from the left child, so we multiply by the left's probability polynomial. We immediately shrink it against the right half's roots to maintain our degree bound. cur_right $$$=$$$ $$$(cur \times Poly_1(l, mid)) \pmod{Poly_2(mid+1, r)}$$$

When we reach a base case $$$l = r$$$, the polynomial cur will be reduced to a degree $$$0$$$ polynomial (a constant), which is exactly our evaluated value $$$P_l$$$.

Complexity

Because the degree of cur is bounded by the size of the current subproblem ($$$r - l + 1$$$), the polynomial multiplication and modulo operations (via Newton's Method; see CP-Algorithms) at this step take only $$$\mathcal{O}((r-l) \log(r-l))$$$ time.

Summing this work over all levels of our divide and conquer recursion yields the classic recurrence relation:

This resolves to an overall time complexity of $$$\mathcal{O}(n \log^2 n)$$$, making it incredibly fast and well within the time limits.

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;

const ll mod = (119 << 23) + 1, root = 62; // = 998244353
ll modpow(ll b, ll e) {
    ll ans = 1;
    for (; e; b = b * b % mod, e /= 2)
        if (e & 1) ans = ans * b % mod;
    return ans;
}

void ntt(vl &a) {
    int n = sz(a), L = 31 - __builtin_clz(n);
    static vl rt(2, 1);
    for (static int k = 2, s = 2; k < n; k *= 2, s++) {
        rt.resize(n);
        ll z[] = {1, modpow(root, mod >> s)};
        rep(i, k, 2 * k) rt[i] = rt[i / 2] * z[i & 1] % mod;
    }
    vi rev(n);
    rep(i, 0, n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
    rep(i, 0, n) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k *= 2)
        for (int i = 0; i < n; i += 2 * k)
            rep(j, 0, k) {
                ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
                a[i + j + k] = ai - z + (z > ai ? mod : 0);
                ai += (ai + z >= mod ? z - mod : z);
            }
}

vl conv(const vl &a, const vl &b) {
    if (a.empty() || b.empty()) return {};
    int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s),
            n = 1 << B;
    int inv = modpow(n, mod - 2);
    vl L(a), R(b), out(n);
    L.resize(n), R.resize(n);
    ntt(L), ntt(R);
    rep(i, 0, n)out[-i & (n - 1)] = (ll) L[i] * R[i] % mod * inv % mod;
    ntt(out);
    return {out.begin(), out.begin() + s};
}

vector<ll> inv(const vector<ll> &a) {
    vector<ll> r = {modpow(a[0], mod - 2)};
    for (int n = 1; n < sz(a); n <<= 1) {
        vector<ll> f(a.begin(), a.begin() + min(sz(a), 2 * n));
        vector<ll> nr = conv(conv(r, r), f);
        r.resize(2 * n);
        for (int i = 0; i < 2 * n; i++)
            r[i] = (2 * r[i] - nr[i] + mod) % mod;
    }
    return r;
}

void normalize(vl &a) {
    while (!a.empty() && a.back() == 0) a.pop_back();
}

vl reverse_poly(const vl &a) {
    vl r = a;
    reverse(all(r));
    return r;
}

// Fixed fast polynomial modulo using Newton's method
vl poly_mod(vl a, const vl &b) {
    normalize(a);
    vl B = b;
    normalize(B);

    if (sz(a) < sz(B)) return a;

    int n = sz(a), m = sz(B);
    int deg_q = n - m;  // degree of quotient

    // Reverse b to get b_rev
    vl b_rev = B;
    reverse(all(b_rev));

    // Compute inverse of b_rev using Newton iteration
    // We need precision of deg_q + 1
    int prec = deg_q + 1;
    vl inv_b = {modpow(b_rev[0], mod - 2)};

    for (int k = 1; k < prec; k *= 2) {
        int new_len = min(2 * k, prec);
        vl b_trunc(b_rev.begin(), b_rev.begin() + min(sz(b_rev), new_len));
        b_trunc.resize(new_len);

        vl prod = conv(inv_b, b_trunc);
        prod.resize(new_len);

        // inv_b := 2 * inv_b - inv_b * b_trunc * inv_b
        vl temp = conv(inv_b, prod);
        temp.resize(new_len);

        inv_b.resize(new_len);
        rep(i, 0, new_len) {
            inv_b[i] = (2 * inv_b[i] - temp[i] + mod) % mod;
        }
    }

    inv_b.resize(prec);

    // Compute quotient: q = reverse(reverse(a) * inv_b_rev)[0..deg_q]
    vl a_rev = a;
    reverse(all(a_rev));

    vl q_rev = conv(a_rev, inv_b);
    q_rev.resize(prec);

    vl q = q_rev;
    reverse(all(q));

    // Compute remainder: r = a - q * b
    vl qb = conv(q, B);

    vl r(m - 1);
    rep(i, 0, m - 1) {
        ll val = a[i];
        if (i < sz(qb)) val = (val - qb[i] + mod) % mod;
        r[i] = val;
    }

    normalize(r);
    return r;
}

ll eval(const vl& a, ll x){
    ll x1=1,ans=0;
    for(auto &i:a){
        ans=(ans+i*x1)%mod;
        x1=x1*x%mod;
    }
    return ans;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        vector<ll> a(n - 1), c(n);
        for (int i = 0; i < n - 1; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> c[i];
        }
        vl a1 = a;
        for (int i = 1; i < n - 1; ++i) {
            a1[i] = (a1[i] + a1[i - 1]) % mod;
        }
        std::reverse(a.begin(), a.end());
        std::reverse(a1.begin(), a1.end());
        vector<vl> tree(4 * n),tree2(4*n);
        function<void(int, int, int)> build = [&](int v, int tl, int tr) {
            if (tl == tr) {
                tree[v] = {1, mod-modpow( a1[tl], mod - 2)};
            } else {
                int tm = (tl + tr) / 2;
                build(v * 2, tl, tm);
                build(v * 2 + 1, tm + 1, tr);
                tree[v] = conv(tree[v * 2], tree[v * 2 + 1]);
            }
        };
        build(1, 0, n - 2);
        function<void(int, int, int)> build2 = [&](int v, int tl, int tr) {
            if (tl == tr) {
                tree2[v] = {mod-a[tl], 1};
            } else {
                int tm = (tl + tr) / 2;
                build2(v * 2, tl, tm);
                build2(v * 2 + 1, tm + 1, tr);
                tree2[v] = conv(tree2[v * 2], tree2[v * 2 + 1]);
            }
        };
        build2(1, 0, n - 2);
        vl ans(n-1);
        function<void(int, int, int, vl)>solve = [&](ll v, ll l, ll r, vl cur){
            if (l==r){
                cur = conv(cur, {1, mod-modpow( a1[l], mod - 2)});
                ans[l]=eval(cur,a[l]);
                return;
            }
            ll m = (l + r) / 2;
            solve(2*v,l,m, poly_mod(cur,tree2[2*v]));
            cur = conv(cur,tree[2*v]);
            solve(2*v+1,m+1,r, poly_mod(cur,tree2[2*v+1]));
        };
        solve(1,0,n-2,{1});
        std::reverse(ans.begin(), ans.end());
        ans.push_back(1);
        std::reverse(a.begin(), a.end());
        std::reverse(a1.begin(), a1.end());
        for (int i = n-1; i >= 0; --i) {
            ll x = 1;
            for (int j = i+1; j < n-1; ++j) {
                x*=(((1-a[i]* modpow(a1[j],mod-2))%mod)+mod)%mod;
                x%=mod;
            }
        }
        ll an=0;
        for (int i = 0; i < n; ++i) {
            an=(an+c[i]*ans[i])%mod;
        }
        cout<<an<<'\n';
    }

}

Focus on a single group. Since we can reorder arbitrarily, try to minimize how the prefix range grows.
Think when does the prefix max − min actually change?

Consider a group as a sorted segment $$$[l, r]$$$.

Try to think about constructing the optimal permutation in reverse*. At any step, adding an element only increases the range if it becomes a new minimum or maximum.

So in an optimal construction, the last element you add will always be either the smallest or the largest remaining element.

This observation leads to a simple interval DP for computing the cost of a segment.

1) Reducing the problem

We are given $$$n$$$ values and need to partition them into $$$k$$$ groups.

Inside each group, we can reorder freely. So the first task is:

Given a set of values, what is the minimum possible strain?

2) Optimal ordering inside one group

Sort the values of a group:

We want to minimize:

Observation:

• The prefix range only changes when we introduce a new minimum or maximum.
• Therefore, we should delay expanding the range as much as possible.

Key idea:

Build the sequence by adding elements from either end.

This leads to the recurrence:

Base case:

We can compute all values in $$$O(n^2)$$$.

3) Structure of optimal partition

After sorting the entire array, we claim:

Each group corresponds to a contiguous segment.

Reason:

If two groups are interleaved, we can swap elements (uncrossing argument) without increasing cost. Repeating this yields contiguous groups.

So the problem becomes:

Partition the sorted array into $$$k$$$ contiguous segments.

4) DP formulation

Let:

Transition:

Base:

Answer:

Naive complexity:

5) Divide & Conquer optimization

The transition satisfies:

So we can apply divide & conquer DP optimization.

Idea:

• Compute $$$dp[p][mid]$$$
• Search optimal split only in a restricted range
• Recurse on left and right halves

Time complexity:

This corresponds to the one solution which is not intended but is good enough to pass the test cases.

6) SMAWK optimization

Rewrite the transition as:

Define matrix:

We want row minimums.

This matrix is totally monotone, so we can apply SMAWK to find all row minima efficiently.

Result:

• Each DP layer in $$$O(n)$$$
• Total complexity:

This corresponds to the intended solution.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vl = vector<ll>;

const ll INF = 1e18;
const ll MOD = 998244353;

/* ---------- SMAWK ---------- */
template <class Select>
vector<int> smawk(int n, int m, const Select &select) {
    function<vector<int>(const vector<int>&, const vector<int>&)> solve =
        [&](const vector<int> &row, const vector<int> &col) -> vector<int> {
            int sz = row.size();
            if (sz == 0) return {};

            vector<int> c2;
            for (int j : col) {
                while (!c2.empty() && select(row[c2.size() - 1], c2.back(), j))
                    c2.pop_back();
                if ((int)c2.size() < sz)
                    c2.push_back(j);
            }

            vector<int> r2;
            for (int i = 1; i < sz; i += 2)
                r2.push_back(row[i]);

            vector<int> a2 = solve(r2, c2);
            vector<int> ans(sz);

            for (int i = 0; i < (int)a2.size(); i++)
                ans[i * 2 + 1] = a2[i];

            int j = 0;
            for (int i = 0; i < sz; i += 2) {
                ans[i] = c2[j];
                int end = (i + 1 == sz ? c2.back() : ans[i + 1]);
                while (c2[j] != end) {
                    j++;
                    if (select(row[i], ans[i], c2[j]))
                        ans[i] = c2[j];
                }
            }
            return ans;
        };

    vector<int> row(n), col(m);
    iota(row.begin(), row.end(), 0);
    iota(col.begin(), col.end(), 0);

    return solve(row, col);
}

/* ---------- DP Layer using SMAWK ---------- */
vl compute_layer(const vl &prev, const vector<vl> &cost, int layer) {
    int n = prev.size();
    vl cur(n, INF);

    int row_size = n - layer;
    int col_size = n - (layer - 1);

    auto argmin = smawk(row_size, col_size,
        [&](int r, int c1, int c2) {
            int i = layer + r;
            int j1 = (layer - 1) + c1;
            int j2 = (layer - 1) + c2;

            auto get = [&](int j) -> ll {
                if (j >= i || j < 0 || j >= n || prev[j] >= INF)
                    return INF;
                return prev[j] + cost[j + 1][i];
            };

            return get(j2) <= get(j1);
        });

    for (int r = 0; r < row_size; r++) {
        int i = layer + r;
        int j = (layer - 1) + argmin[r];
        if (j < i && j >= 0 && prev[j] < INF)
            cur[i] = prev[j] + cost[j + 1][i];
    }

    return cur;
}

/* ---------- Main ---------- */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, k;
        cin >> n >> k;

        vl a(n);
        for (auto &x : a) cin >> x;
        sort(a.begin(), a.end());

        // Precompute cost
        vector<vl> cost(n, vl(n, INF));
        for (int i = 0; i < n; i++) cost[i][i] = 0;

        for (int len = 1; len < n; len++) {
            for (int l = 0; l + len < n; l++) {
                int r = l + len;
                cost[l][r] = a[r] - a[l] + min(cost[l + 1][r], cost[l][r - 1]);
            }
        }

        // DP
        vector<vl> dp(k, vl(n, INF));
        for (int i = 0; i < n; i++)
            dp[0][i] = cost[0][i];

        for (int i = 1; i < k; i++)
            dp[i] = compute_layer(dp[i - 1], cost, i);

        cout << dp[k - 1][n - 1] << '\n';
    }
}

Consider you have the answer of length $$$i$$$, how can you find the length of $$$i+1$$$?

You can get the answer of $$$i+1$$$ from answer of $$$i$$$ by prepending or appending a $$$0$$$ or $$$1$$$. WLOG, if we assume we prepend, in what specific cases will adding a $$$0$$$ or a $$$1$$$ actually increase the length of the longest non-decreasing subsequence?

Let $$$E_i$$$ represent the expected value of the LNDS of a string of length $$$i$$$.

Let's say we prepend a character to the start of a string of length $$$i-1$$$. If we prepend a 0, it will always contribute to the longest subsequence, giving a guaranteed $$$+1$$$ to the length.

If we prepend a 1, it will only contribute if the entire longest non-decreasing subsequence of the remaining string consists only of 1s. This gives us a new subproblem: In which cases does a string have entirely 1s as its optimal subsequence?

Consider any prefix of the string. If a prefix has more 0s than 1s, we could simply take those 0s and improve our LNDS length. Therefore, a necessary and sufficient condition for the LNDS to be entirely 1s is that for every prefix, the count of 0s is $$$\le$$$ the count of 1s.

How do we count the number of such strings? This is a classic application of Bertrand's ballot theorem (which relies on the reflection principle).

Let $$$N = i-1$$$. We want to find the number of paths of length $$$N$$$ where the number of 1s minus the number of 0s never drops below zero. The total number of paths of length $$$N$$$ that end at a difference of $$$y$$$ is $$$\binom{N}{\frac{N+y}{2}}$$$. By the reflection principle, the number of valid paths ending at $$$y$$$ that never dip below zero is $$$\binom{N}{\frac{N+y}{2}} - \binom{N}{\frac{N+y+2}{2}}$$$.

To find all valid strings, we sum this over all possible valid ending differences $$$y \ge 0$$$. Notice how the sum telescopically cancels out:

If $$$N$$$ is even ($$$y = 0, 2, 4, \dots$$$):

If $$$N$$$ is odd ($$$y = 1, 3, 5, \dots$$$):

So we can say number of valid strings are: $$$\binom{N}{\lfloor N/2 \rfloor}$$$. Substituting $$$N = i-1$$$ back in, the number of valid strings is $$$\binom{i-1}{\lfloor (i-1)/2 \rfloor}$$$.

Since there are $$$2^{i-1}$$$ total possible strings of length $$$i-1$$$, the probability of getting one of these valid strings is $$$\frac{\binom{i-1}{\lfloor (i-1)/2 \rfloor}}{2^{i-1}}$$$.

This gives us this final transition:

Which simplifies to:

If we unroll this recurrence relation from $$$i = 1$$$ to $$$n$$$, the $$$\frac{1}{2}$$$ term simply adds up $$$n$$$ times. Therefore, the final expected value for a string of length $$$n$$$ can be directly computed as the sum:

#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

ll MOD;
ll bin_exp(ll a, ll b, ll mod) {
    a %= mod;
    ll ans = 1;
    while (b > 0) {
        if (b & 1) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

ll inv(ll x) { return bin_exp(x % MOD, MOD - 2, MOD); }

void solve() {
    ll n;
    cin >> n >> MOD;
    vector<ll> fact(n + 1), invfact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invfact[n] = inv(fact[n]);
    for (ll i = n - 1; i >= 0; i--)
        invfact[i] = (invfact[i + 1] * (i + 1)) % MOD;

    auto nCr = [&](ll n, ll r) ->ll {
        if (r < 0 || r > n)
            return 0;
        return ((((fact[n]) % MOD * invfact[r]) % MOD) * invfact[n - r]) % MOD;
        };

    ll inv2 = inv(2);
    ll cur = inv2 * inv2 % MOD;

    ll tot = inv2;
    for(int i = 1; i < n; i++){
        tot = (tot + nCr(i, i / 2) * cur % MOD) % MOD;
        cur = cur * inv2 % MOD;
    }

    tot = (tot + (n * inv(2)) % MOD) % MOD;
    cout << tot << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Think about a spanning tree that maximizes the absolute value of the product of its edge weights. A natural idea is to run Kruskal’s algorithm on the edges sorted by decreasing $$$|w|$$$.

We build the spanning tree that maximizes the absolute product, then the sign becomes important.
If the product is already negative, we are done.
If it is positive, we try to make it negative.

For every non-tree edge $$$(u, v, w)$$$, adding it creates a cycle. We may remove one edge from the path between $$$u$$$ and $$$v$$$ in the tree.

• If $$$w \gt 0$$$, we need a negative edge on that path.
• If $$$w \lt 0$$$, we need a positive edge on that path.
• If $$$w = 0$$$, then the answer is immediately $$$0$$$.

Among all valid swaps, we want the one that makes the final negative product as small as possible.

We need to find a spanning tree with the minimum product of edge weights.

Observation 1: The abs-MST maximizes |product|

Let us build a spanning tree using Kruskal’s algorithm on edges sorted by decreasing $$$|w|$$$.
Call this tree the abs-MST.

We claim that the abs-MST has the maximum possible value of $$$|product|$$$ among all spanning trees.

To see this, take the abs-MST $$$T$$$ and any other spanning tree $$$T'$$$.
Sort the edges of both trees in decreasing order of absolute value:

• $$$|e_1| \ge |e_2| \ge \dots \ge |e_{n-1}|$$$ for $$$T$$$
• $$$|f_1| \ge |f_2| \ge \dots \ge |f_{n-1}|$$$ for $$$T'$$$

We claim that for every $$$i$$$, $$$|e_i| \ge |f_i|$$$.

If not, let $$$i$$$ be the first position where $$$|e_i| \lt |f_i|$$$.
Then $$$T'$$$ has at least $$$i$$$ edges with absolute value at least $$$|f_i|$$$.
But $$$T$$$ was built greedily by Kruskal on decreasing $$$|w|$$$, so it must also contain at least $$$i$$$ such edges.
This contradicts the fact that $$$|e_i|$$$ is the $$$i$$$-th largest edge in $$$T$$$.

Hence $$$|e_i| \ge |f_i|$$$ for all $$$i$$$, so:

Therefore the abs-MST maximizes the absolute value of the product.

Observation 2: The sign of the abs-MST determines the answer

Let $$$P$$$ be the product of the abs-MST.

There are three cases:

• $$$P = 0$$$: the answer is $$$0$$$.
• $$$P \lt 0$$$: the abs-MST is already the answer, because it has the largest absolute product and is negative, so it is the most negative possible value.
• $$$P \gt 0$$$: we want to make the product negative if possible, because any negative number is smaller than any positive number.

So the only hard case is when the abs-MST product is positive.

Observation 3: One edge swap is enough to try

Why is a single swap always optimal?

Suppose we change the sign of the product by swapping a set of $$$k$$$ tree edges $$$(e_1, e_2, \dots, e_k)$$$ with $$$k$$$ non-tree edges $$$(n_1, n_2, \dots, n_k)$$$.

Because our initial tree is the Maximum Absolute Spanning Tree, every non-tree edge $$$n_i$$$ used to reconnect the tree after removing $$$e_i$$$ must satisfy:

Otherwise, $$$n_i$$$ would have been chosen earlier by Kruskal and would belong to the maximum absolute spanning tree.

So each swap can only decrease (or keep) the absolute product of the tree.

Now, if these $$$k$$$ swaps manage to flip the sign of the product, then at least one of them must involve edges of opposite signs. Since every extra swap only makes the absolute value smaller, the best choice is to perform only the single swap that flips the sign.

Take any non-tree edge $$$e = (u, v, w_e)$$$.
When we add it to the tree, it creates a unique cycle.
We can remove one edge $$$f$$$ on the path between $$$u$$$ and $$$v$$$ to get another spanning tree. The new product is:

To make $$$P_{new}$$$ negative, we need $$$w_e$$$ and $$$w_f$$$ to have opposite signs.

So:

• if $$$w_e \gt 0$$$, we need a negative tree edge on the path;
• if $$$w_e \lt 0$$$, we need a positive tree edge on the path.

Among all such swaps, we want the final product to be as small as possible.
That means we want the most negative value, i.e. the largest possible absolute value after the sign flip.

Since:

we want to maximize $$$\frac{|w_e|}{|w_f|}$$$.

So for each non-tree edge, we should find the best opposite-sign edge on the path.

Observation 4: Path queries with LCA

For every non-tree edge $$$(u, v, w_e)$$$:

• If $$$w_e \gt 0$$$, we need the largest negative edge on the path from $$$u$$$ to $$$v$$$, i.e. the negative edge closest to $$$0$$$.
• If $$$w_e \lt 0$$$, we need the smallest positive edge on the path from $$$u$$$ to $$$v$$$, i.e. the positive edge closest to $$$0$$$.
• If $$$w_e = 0$$$, then the answer is $$$0$$$ immediately.

We can answer these path queries using binary lifting.

For each node and each $$$2^k$$$ ancestor jump, store:

• the best negative edge on that jump,
• the best positive edge on that jump.

When merging two segments:

• for negative values, keep the larger one (closest to $$$0$$$);
• for positive values, keep the smaller one (closest to $$$0$$$).

This allows us to answer each path query in $$$\mathcal{O}(\log n)$$$.

What if no sign flip is possible?

If none of the non-tree edges can create a negative product, then all spanning trees have positive product.
In that case, we simply need the minimum positive product, which is obtained by running Kruskal on edges sorted by increasing $$$|w|$$$.

Algorithm

1. Sort edges by decreasing $$$|w|$$$ and run Kruskal to build the abs-MST.
2. Compute the product of its edges modulo $$$10^9+7$$$ and also determine its sign.
3. If the product is $$$0$$$, print $$$0$$$.
4. If the product is negative, print it modulo $$$10^9+7$$$.
5. Otherwise, the product is positive:

• preprocess the tree with LCA + binary lifting,
• for every non-tree edge, query the path for the best opposite-sign edge,
• keep the swap that maximizes $$$|w_e| / |w_f|$$$,
• if such a swap exists, output the corresponding negative product,
• otherwise build the minimum abs spanning tree and output its product.

Complexity

• Sorting: $$$\mathcal{O}(m \log m)$$$
• Kruskal: $$$\mathcal{O}(m \alpha(n))$$$
• LCA preprocessing: $$$\mathcal{O}(n \log n)$$$
• Each path query: $$$\mathcal{O}(\log n)$$$

Total: $$$\mathcal{O}(m \log m + m \log n)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

ll pow(ll a, ll b, ll c) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % c;
        b >>= 1;
        a = (a * a) % c;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        ll m;
        cin >> m;

        vector<vector<array<ll, 2>>> adj(n);
        vector<array<ll, 4>> edges(m);

        for (int i = 0; i < m; i++) {
            ll u, v, w;
            cin >> u >> v >> w;
            u--;
            v--;
            edges[i] = {abs(w), w, u, v};
        }

        sort(edges.begin(), edges.end());
        reverse(edges.begin(), edges.end());

        ll x = 1, y = 1;

        vector<ll> par(n), sz(n, 1);
        iota(par.begin(), par.end(), 0);

        function<ll(ll)> find = [&](ll u) -> ll {
            return par[u] == u ? u : par[u] = find(par[u]);
        };

        auto merge = [&](ll u, ll v) -> void {
            u = find(u);
            v = find(v);
            if (u == v) return;
            if (sz[u] < sz[v]) swap(u, v);
            par[v] = u;
            sz[u] += sz[v];
        };

        for (auto &[_, w, u, v] : edges) {
            if (find(u) == find(v)) continue;
            merge(u, v);
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
            if (w == 0) {
                x = y = 0;
                break;
            }
            x *= w / _;
            y *= w + mod;
            y %= mod;
        }

        if (x <= 0) {
            cout << y << '\n';
        } else {
            vector<vector<ll>> up(20, vector<ll>(n, -1)),
                               minup(20, vector<ll>(n, 1)),
                               maxup(20, vector<ll>(n, -1));

            vector<ll> tin(n), tout(n);
            ll timer = 0;

            function<void(ll, ll)> dfs = [&](ll u, ll p) -> void {
                up[0][u] = p;
                tin[u] = timer++;

                for (int i = 1; i < 20; i++) {
                    if (up[i - 1][u] == -1) break;
                    up[i][u] = up[i - 1][up[i - 1][u]];

                    if (minup[i - 1][u] < 0 && minup[i - 1][up[i - 1][u]] < 0)
                        minup[i][u] = max(minup[i - 1][u], minup[i - 1][up[i - 1][u]]);
                    else
                        minup[i][u] = min(minup[i - 1][u], minup[i - 1][up[i - 1][u]]);

                    if (maxup[i - 1][u] > 0 && maxup[i - 1][up[i - 1][u]] > 0)
                        maxup[i][u] = min(maxup[i - 1][u], maxup[i - 1][up[i - 1][u]]);
                    else
                        maxup[i][u] = max(maxup[i - 1][u], maxup[i - 1][up[i - 1][u]]);
                }

                for (auto &[v, w] : adj[u]) {
                    if (v == p) continue;
                    if (w < 0) minup[0][v] = w;
                    else maxup[0][v] = w;
                    dfs(v, u);
                }

                tout[u] = timer;
            };

            dfs(0, 0);

            auto is_ancestor = [&](ll u, ll v) -> bool {
                return tin[u] <= tin[v] && tout[u] >= tout[v];
            };

            auto lca = [&](ll u, ll v) -> ll {
                if (is_ancestor(u, v)) return u;
                if (is_ancestor(v, u)) return v;
                for (int i = 19; i >= 0; i--) {
                    if (up[i][u] != -1 && !is_ancestor(up[i][u], v)) {
                        u = up[i][u];
                    }
                }
                return up[0][u];
            };

            auto query = [&](ll u, ll v) -> pair<ll, ll> {
                ll minw = 1, maxw = -1;
                ll l = lca(u, v);

                for (int i = 19; i >= 0; i--) {
                    if (!is_ancestor(up[i][u], l)) {
                        if (minup[i][u] < 0 && minw < 0) minw = max(minw, minup[i][u]);
                        else minw = min(minw, minup[i][u]);

                        if (maxup[i][u] > 0 && maxw > 0) maxw = min(maxw, maxup[i][u]);
                        else maxw = max(maxw, maxup[i][u]);

                        u = up[i][u];
                    }
                }

                for (int i = 19; i >= 0; i--) {
                    if (!is_ancestor(up[i][v], l)) {
                        if (minup[i][v] < 0 && minw < 0) minw = max(minw, minup[i][v]);
                        else minw = min(minw, minup[i][v]);

                        if (maxup[i][v] > 0 && maxw > 0) maxw = min(maxw, maxup[i][v]);
                        else maxw = max(maxw, maxup[i][v]);

                        v = up[i][v];
                    }
                }

                if (u != l) {
                    if (minup[0][u] < 0 && minw < 0) minw = max(minw, minup[0][u]);
                    else minw = min(minw, minup[0][u]);

                    if (maxup[0][u] > 0 && maxw > 0) maxw = min(maxw, maxup[0][u]);
                    else maxw = max(maxw, maxup[0][u]);
                }

                if (v != l) {
                    if (minup[0][v] < 0 && minw < 0) minw = max(minw, minup[0][v]);
                    else minw = min(minw, minup[0][v]);

                    if (maxup[0][v] > 0 && maxw > 0) maxw = min(maxw, maxup[0][v]);
                    else maxw = max(maxw, maxup[0][v]);
                }

                return {minw, maxw};
            };

            array<ll, 2> a{-1, 1};

            for (auto &[_, w, u, v] : edges) {
                auto [minw, maxw] = query(u, v);

                if (w > 0) {
                    if (minw * w < 0) {
                        w = abs(w);
                        minw = abs(minw);
                        if (a[0] * minw < w * a[1]) {
                            a = {w, minw};
                        }
                    }
                } else if (w < 0) {
                    if (maxw * w < 0) {
                        w = abs(w);
                        maxw = abs(maxw);
                        if (a[0] * maxw < w * a[1]) {
                            a = {w, maxw};
                        }
                    }
                } else {
                    if (a[0] < 0) a = {0, 1};
                }
            }

            if (a[0] >= 0) {
                cout << (mod - (((y * a[0]) % mod * pow(a[1], mod - 2, mod)) % mod)) % mod << '\n';
            } else {
                reverse(edges.begin(), edges.end());
                sz.assign(n, 1);
                iota(par.begin(), par.end(), 0);
                y = 1;

                for (auto &[_, w, u, v] : edges) {
                    if (find(u) == find(v)) continue;
                    merge(u, v);
                    y *= w + mod;
                    y %= mod;
                }

                cout << y << '\n';
            }
        }
    }

    return 0;
}

Trivially, if $$$a = b$$$, there is no valid solution. WLOG, assume $$$a \lt b$$$.

If $$$a \lt b$$$, we have $$$a \bmod b = a$$$ and $$$b \bmod a \lt a$$$.

Trivially, if $$$a = b$$$, there is no valid solution. WLOG, assume $$$a \lt b$$$.

If $$$a \lt b$$$, we have $$$a \bmod b = a$$$ and $$$b \bmod a \lt a$$$. This implies that $$$(a \bmod b) + (b \bmod a) \lt 2a$$$. From the given equation, we must have $$$a | b \lt 2a$$$, which forces the condition $$$\text{msb}(b) \le \text{msb}(a)$$$. From our assumption $$$a \lt b$$$, the condition further simplifies to $$$\text{msb}(b) = \text{msb}(a)$$$.

Note that if $$$\text{msb}(b) = \text{msb}(a)$$$, we must have $$$b \lt 2a$$$. Thus, $$$a \lt b \lt 2a$$$. This makes $$$(b \bmod a) = b - a$$$. Hence, the given equation reduces to $$$b = (a | b)$$$, $$$\text{msb}(b) = \text{msb}(a)$$$.

For counting the number of pairs, we can iterate over all possible values of $$$b$$$ from $$$1$$$ to $$$n$$$ and find the number of sub-masks of $$$b$$$ that are not more than $$$m$$$ and have the same $$$\text{msb}$$$. Now, we repeat the same process and find the number of pairs with $$$a \gt b$$$.

Claim : The height of the tree equals the depth of vertex $$$n$$$ for any valid array.
Think about whether the sequence $$$depth(0), depth(1), \ldots, depth(n)$$$ is non-decreasing.

Since $$$h(a) = depth(n)$$$ always, the answer is just $$$\sum_a depth_a(n)$$$. Split arrays of size $$$n$$$ into two halves by the value of $$$a[n]$$$. In each half, express $$$depth(n)$$$ in terms of $$$depth(n-1)$$$ or $$$depth(n-2)$$$ and derive a recurrence for the sum.

Let $$$dp[n] = \sum_a depth_a(n)$$$ over all valid arrays of size $$$n$$$. Since $$$h(a) = depth(n)$$$, this is exactly the answer.

There are $$$2^{n-1}$$$ valid arrays ($$$a[1] = 0$$$ fixed, $$$a[2], \ldots, a[n]$$$ free). Split by the value of $$$a[n]$$$:

Case $$$a[n] = 0$$$ (vertex $$$n$$$ connects to $$$n-1$$$): $$$depth(n) = depth(n-1) + 1$$$. There are $$$2^{n-2}$$$ such arrays, and $$$a[n]$$$ does not affect $$$\text{depth}(n-1)$$$, so:

Case $$$a[n] = 1$$$ (vertex $$$n$$$ connects to $$$n-2$$$): $$$depth(n) = depth(n-2) + 1$$$. There are $$$2^{n-2}$$$ such arrays; $$$a[n-1]$$$ is free and does not affect $$$depth(n-2)$$$, this means $$$depth(n-2)$$$ will be counted twice for each value of $$$a[n-1]$$$, so:

Adding both cases:

with base cases $$$dp[0] = 0$$$, $$$dp[1] = 1$$$.

Complexity: $$$O(n_{\max})$$$ with precomputation.

How many times can the prefix $$$\gcd$$$ sequence $$$x_i = \gcd(a_1,\dots,a_i)$$$ change?

It changes at most $$$O(\log A)$$$ times since each change makes it at least half.

After removing one element from a segment, what condition must the remaining $$$\gcd$$$ satisfy to become a target value after one modification?

You need:

where $$$g$$$ is the $$$\gcd$$$ after removal and $$$t$$$ is the target.

Define a function

For each index $$$i$$$, let

and define

We need to count all $$$i$$$ such that $$$f(P_i, S_i) = 1$$$.

A modification consists of changing at most one element in $$$P_i \cup S_i$$$. Observe that changing an element is equivalent to removing it and replacing it with a suitable value, hence it suffices to consider removal.

Thus, for a fixed $$$i$$$, the following cases arise:

(1) No modification:

(2) One removal in prefix: There exists $$$j \le i$$$ such that

(3) One removal in suffix: There exists $$$k \gt i$$$ such that

Hence,

How to check efficiently

Instead of recomputing $$$\gcd$$$ after removing each element, observe:

To make $$$\gcd$$$ equal to $$$g$$$ after removing at most one element, it is necessary and sufficient that all elements except at most one are divisible by $$$g$$$.

Thus: - For prefix check, count elements $$$j \le i$$$ such that $$$a_j \bmod y_i \ne 0$$$ - For suffix check, count elements $$$j \gt i$$$ such that $$$a_j \bmod x_i \ne 0$$$

If the count $$$\le 1$$$, the condition holds.

Using the property that prefix/suffix $$$\gcd$$$ take at most $$$O(\log A)$$$ distinct values, we only recompute these counts when the $$$\gcd$$$ changes.

Each such recomputation scans the array once, so total work is $$$O(n)$$$ per distinct $$$\gcd$$$.

Since there are at most $$$O(\log A)$$$ distinct values, total complexity becomes:

Lemma 1. (Prefix $$$\gcd$$$ changes $$$O(\log A)$$$ times)

Let $$$x_i = \gcd(a_1,\dots,a_i)$$$. Then $$$x_i$$$ takes $$$O(\log A)$$$ distinct values.

Proof.

If $$$x_{i+1} \ne x_i$$$, then $$$x_{i+1}$$$ is a proper divisor, so:

Thus after $$$k$$$ changes: $$$x_i \le A/2^k \ge 1 \Rightarrow k \le \log_2 A$$$.

Lemma 2. (Divisibility condition is sufficient and necessary)

Let $$$g = \gcd(P_i \setminus {a_j})$$$. Then one modification makes $$$\gcd(P_i)=y_i$$$ iff:

Proof.

If $$$y_i \mid g$$$, replace $$$a_j$$$ with $$$y_i$$$: $$$\gcd(g, y_i) = y_i$$$

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve()
{
    int n;
    cin >> n;

    vector<ll> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    vector<ll> pref(n), suff(n);

    ll g = 0;
    for (int i = 0; i < n; i++)
    {
        g = __gcd(g, a[i]);
        pref[i] = g;
    }

    g = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        g = __gcd(g, a[i]);
        suff[i] = g;
    }

    vector<int> pref_ok(n), suff_ok(n);

    g = 0;
    int bad = 0;

    for (int i = 0; i < n - 1; i++)
    {
        ll ng = __gcd(g, a[i]);

        if (ng != g)
        {
            int cnt = 0;
            for (int j = i + 1; j < n; j++)
            {
                if (a[j] % ng != 0)
                {
                    cnt++;
                }
            }
            pref_ok[i] = (cnt <= 1);
        }
        else
        {
            pref_ok[i] = (i ? pref_ok[i - 1] : 0);
        }

        g = ng;
    }

    g = 0;

    for (int i = n - 1; i > 0; i--)
    {
        ll ng = __gcd(g, a[i]);

        if (ng != g)
        {
            int cnt = 0;
            for (int j = 0; j < i; j++)
            {
                if (a[j] % ng != 0)
                {
                    cnt++;
                }
            }
            suff_ok[i - 1] = (cnt <= 1);
        }
        else
        {
            suff_ok[i - 1] = (i + 1 < n ? suff_ok[i] : 0);
        }

        g = ng;
    }

    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        ll x = pref[i];
        ll y = (i + 1 < n ? suff[i + 1] : 0);

        if (i + 1 < n && x == y)
        {
            ans++;
            continue;
        }

        if (pref_ok[i] || suff_ok[i])
        {
            ans++;
        }
    }

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}