If we have a square $$$s$$$ and another square $$$S$$$ that completely covers $$$s$$$, then the intersection of $$$s$$$ and $$$S$$$ is a valid square.

Recall that we can pick any valid square, so long as the coordinates for both axes are in the range $$$[-10^9, 10^9]$$$.

Note that all coordinates for our squares are in the range $$$[-10^9, 10^9]$$$. Also, consider that we are allowed to print any square that satisfies the condition in the problem statement.

Consider Hint 1: if another square completely covers one square, then their intersection remains a square. Thus, the easiest construction is for our square $$$S$$$ to cover all the input squares completely.

Because of this, we can print a square with its lower-left corner at $$$(-10^9, -10^9)$$$ and its upper-right corner at $$$(10^9, 10^9)$$$.

inf = 10**9
print(-inf, -inf, inf, inf)

How do you find the optimal path? Think greedy.

The $$$\text{MEX}$$$ is the smallest number not present in the path. You already have the optimal path. Recall that all values from $$$0$$$ to $$$n + 1$$$ are present.

The key observation is that you should always take the smallest number in each layer: if you were to take another number in the layer, the evaluation score must be at most the smallest number in that layer.

To show that this is true, suppose we chose the path containing the minimum value in each layer. Let's denote the $$$\text{MEX}$$$ as $$$m$$$. For each layer, let's denote the minimum value $$$a_i$$$ where $$$i$$$ is the layer. If $$$a_i \lt m$$$, we cannot choose any other node in that layer, since the $$$\text{MEX}$$$ will become $$$a_i$$$. Otherwise, if $$$a_i \gt m$$$, it is impossible for $$$m$$$ to be in that layer, since we know $$$a_i$$$ to be the minimum value in that layer.

Knowing this, how do we find the $$$\text{MEX}$$$? One solution is to put all the chosen elements in an array and check for the smallest missing value. Another option is to notice that since all values $$$0$$$ to $$$n + 1$$$ are present, the $$$\text{MEX}$$$ must be in one of the layers. Thus, you can simply look at the second smallest value for every layer — the smallest of these will be the $$$\text{MEX}$$$. The only edge case occurs when each layer consists of only one number; the answer is just $$$n + 2$$$.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    int network[d + 2];
    network[0] = 0;
    network[d + 1] = n + 1;
    for (int i = 1; i <= d; i++) {
        int m;
        cin >> m;
        int smallest = n + 5;
        for (int j = 0; j < m; j++) {
            int v;
            cin >> v;
            smallest = min(smallest, v);
        }
        network[i] = smallest;
    }
    sort(network, network + d + 2);
    for (int i = 0; i < d + 2; i++) {
        if (network[i] != i) {
            cout << i << "\n";
            return 0;
        }
    }
    cout << n + 2 << "\n";
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    int ans = n + 2;
    for (int i = 0; i < d; i++) {
        int m;
        cin >> m;
        int s = n + 2;
        int ss = n + 2;
        for (int i = 0; i < m; i++) {
            int v;
            cin >> v;
            if (v < s) {
                ss = s;
                s = v;
            } else if (v < ss) ss = v;
        }
        ans = min(ans, ss);
    }
    cout << ans << "\n";
    return 0;
}

The amount of snow that accumulates on the tree is equal to the amount of snow that falls per day multiplied by the number of days it takes before the tree breaks.

The number of days before any individual node breaks is independent of the other nodes in the tree.

Each node will break after $$$\lfloor \frac{\text{strength}}{\text{weight of subtree}} \rfloor$$$ days. Greedily, it is optimal to strengthen the $$$k$$$ nodes which will break first. To calculate the weight of each node's subtree, we can use depth-first-search. Then, create an array storing each node's breaking point. Sort this array to determine the order in which to strengthen nodes.

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2e5;

int w[MAXN], a[MAXN], days[MAXN];
vector<int> adj[MAXN];

long long dfs(int i, int p){
    long long subtree = a[i];

    for(int j : adj[i]) if(j != p)
    	subtree += dfs(j, i);

    days[i] = w[i]/subtree;

    return subtree;
}

int main(){
    int n; cin >> n;

    for(int i=0; i<n; ++i) cin >> w[i];
    for(int i=0; i<n; ++i) cin >> a[i];

    for(int i=1; i<n; ++i){
    	int u, v; cin >> u >> v;
    	adj[u-1].push_back(v-1);
    	adj[v-1].push_back(u-1);
    }

    long long total = dfs(0, 0);

    sort(days, days+n);

    for(int i=0; i<n; ++i)
    	cout << total*days[i] << '\n';
}

Alice is able to determine what move Bob makes as Bob can only make one move to maximize the results.

Because Alice may choose only one entry of $$$A$$$, every other position has a fixed contribution we can precompute — specifically, how large the result would be if Bob chose that index after Alice's move. For any choice $$$i$$$ that Alice makes, Bob will pick whichever gives a larger value: either he picks $$$j = i$$$, or he picks the best index among all $$$j \neq i$$$. Alice's goal after that is to pick an index $$$i$$$ that minimizes this worse-case value.

To evaluate the best index among all $$$j \neq i$$$ efficiently for every i, we can compute the two largest values of $$$f(j) = A_j | (y-A_j)$$$ over all $$$j$$$. For a given index $$$i$$$, if the overall maximum $$$f(j)$$$ comes from $$$j = i$$$, then the best choice among the remaining indices is the second-largest. Otherwise, the best choice is the largest. Using this idea, we can check every $$$i$$$ in constant time after the initial scan, giving an $$$O(n)$$$ solution.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    while(t--){
        int n; ll x, y;
        cin >> n >> x >> y;

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

        vector<ll> loss(n);
        for(int i = 0; i < n; ++i) loss[i] = vals[i]-(vals[i]&y);

        ll min1 = LLONG_MAX, min2 = LLONG_MAX;
        int idx1 = -1;
        for(int i = 0; i < n; ++i) {
            if(loss[i] < min1){
                min2 = min1;
                min1 = loss[i];
                idx1 = i;
            } else if(loss[i] < min2) {
                min2 = loss[i];
            }
        }

        ll ans = LLONG_MAX;
        for(int i = 0; i < n; ++i) {
            ll alice = vals[i]|x;
            ll delta = alice-vals[i], same = alice-(alice&y);
            ll obest = ((i == idx1) ? min2 : min1);
            ll bob = min(obest, same);
            ll temp = sum+delta-bob;
            ans = min(ans, temp);
        }

        cout << ans << "\n";
    }

    return 0;
}

Recall that the trolleys are sorted such that the heaviest trolleys go first, and the lightest ones go last. If a trolley gets stopped by a cow, what does that mean for the rest of the trolleys?

If we have a trolley get stopped by a cow, then we can direct subsequent trolleys to the same cow.

Once we have one cow that can stop a trolley, all subsequent trolleys can be directed to that same cow. This means that in our array of trolleys, we will have some prefix of trolleys that won't awaken a cow, while the rest of the trolleys will result in us waking up a cow.

Let's consider binary searching on the longest prefix of trolleys that won't awaken a cow. Consider checking if a prefix length of $$$m$$$ is valid.

Let the weight of the heaviest trolley in our prefix be $$$x$$$. We need to find the minimum index $$$i$$$, such that either $$$c[i] \geq x$$$ or $$$d[i] \geq x$$$.

If we are zero-indexing, $$$i$$$ is equal to the number of cows that must be awoken before finally reaching a cow heavy enough to stop our prefix of trolleys.

As long as $$$i$$$ is less than $$$n - m$$$, the number of trolleys not in our prefix, we can force all $$$m$$$ trolleys into a cow that is heavy enough.

Thus, with this condition, we can binary search on the longest prefix. The answer is then the number of trolleys that aren't in our prefix. With that, we can solve the problem in $$$\mathcal{O}(n \log n)$$$ time.

Note that an $$$\mathcal{O}(n)$$$ solution exists, but is slightly more difficult to implement.

#include <bits/stdc++.h>

using ll = long long;

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

    int n, a, b;
    std::cin >> n >> a >> b;
    std::vector<int> t(n), c(a), d(b);
    for (auto &i : t) std::cin >> i;
    for (auto &i : c) std::cin >> i;
    for (auto &i : d) std::cin >> i;

    int lo = 0, hi = n;
    while (lo < hi) {
        int m = (lo + hi + 1) / 2;

        int biggest = (m == 0) ? -1 : t[m - 1];
        int get_hit = std::min(a, b);

        for (int i = 0; i < a; i++) {
            if (biggest <= c[i]) get_hit = std::min(get_hit, i);
        }

        for (int i = 0; i < b; i++) {
            if (biggest <= d[i]) get_hit = std::min(get_hit, i);
        }

        if (get_hit <= n - m) lo = m;
        else hi = m - 1;
    }

    std::cout << n - lo << '\n';
}

We can write a set of equations to describe this.

Well, we already have a set of equations, surely the solution is just deterministic with some constraints based on the setup right?

Let's set the original series of $$$5$$$ numbers to be $$$a_1, a_2, a_3, a_4, a_5$$$ and the number of operations to be $$$x_1, x_2, x_3, y_1, y_2$$$ (where $$$x_i$$$ is the number of first operations that starts at the $$$i$$$th number, $$$y_i$$$ is the number of second operations that starts at the $i$th number). Rewriting the problem statement as mathematical statements gives us the following:

We observe that $$$a_{1...5}$$$ are all constants, so we are solving $$$x_{1, 2, 3}$$$ and $$$\space y_{1, 2}$$$ with $$$5$$$ equations, which is clearly deterministic.

We can rewrite $$$x_{1, 2, 3}$$$ and $$$\space y_{1, 2}$$$ in terms of $$$a_{1...5}$$$

Now, If any of $$$x_{1, 2, 3}$$$ or $$$\space y_{1, 2}$$$ is negative, you won't have a solution (since we can't add). Otherwise, output $$$(x_1 + x_2 + x_3) * 1* + (y_1 + y_2) * 2$$$.

Note: due to the constraint of the problem being on the sum of the integers, individual number or final cost may exceed the limit of regular 32 bit integer. Thus, we should use 64 bit integer, like long long in C++.

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

#define ll long long

void solve() {
    ll a1, a2, a3, a4, a5;
    cin >> a1 >> a2 >> a3 >> a4 >> a5;

    ll x1 = a3 - a4, x2 = a3 - a1 - a5, x3 = a3 - a2;
    ll y1 = a1 + a4 - a3, y2 = a2 + a5 - a3;

    if (x1 < 0 || x2 < 0 || x3 < 0 || y1 < 0 || y2 < 0)
        cout << -1 << '\n';
    else
        cout << x1 + x2 + x3 + (y1 + y2) * 2 << '\n';
    return;
}

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

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

    return 0;
}

Think of the maximum width $$$w$$$ as the number of nodes on the widest level. If you try to build such a tree topΓÇôdown, you need extra nodes above to ΓÇ£supportΓÇ¥ that level.

Given a candidate width $$$w$$$, how many nodes are needed in total? Start with $$$w$$$ on some level, then half of them on the level above, then half again, and so on until reaching 1. If the total $$$\leq n$$$, then width $$$w$$$ is achievable.

We binary search on the answer $$$w$$$; For a mid value $$$w$$$, compute how many nodes are required: $$$ \text{cur} = w + \left\lceil \tfrac{w}{2} \right\rceil + \left\lceil \tfrac{w}{4} \right\rceil + \dots + 1 $$$. If $$$\text{cur} \leq n$$$, then $$$w$$$ is possible, otherwise itΓÇÖs too large. The largest valid $$$w$$$ found is the answer.

This runs in $$$O(\log n \cdot \log n)$$$ per test case, fast enough for $$$n \leq 10^9$$$.

#include <bits/stdc++.h>
#define int long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms(a, b) memset(a, b, sizeof (a))
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
template <typename T> bool chkmin (T &a, T b) {
	return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T &a, T b) {
	return (b > a) ? a = b, 1 : 0;
}
using namespace std;
int T, n;
signed main () {
	cout << fixed << setprecision (0);
	ios :: sync_with_stdio (0), cin.tie (0), cout.tie (0);
	int l, r;
	cin >> T;
	wh (T) {
		cin >> n;
		l = 1, r = n;
		while (l < r) {
//			cout << l << " " << r << "\n";
			int mid = l + r + 1 >> 1;
			int cur = 1, x = mid;
			while (x > 1) cur += x, (++ x) /= 2;
			if (cur <= n) l = mid;
			else r = mid - 1;
		}
		cout << l << "\n";
	}
	return 0;
}

Try to figure out, for each element, the largest subarray length where it stays the maximum. You can do this using next greater to left/right with a monotone stack.

Once you know the max length $$$L$$$ for each element, that element is a candidate maximum for every subarray size $$$k \leq L$$$. Collect these contributions for all $$$k$$$.

Each $$$a_i$$$ dominates an interval between its next greater elements to the left and right. That gives the maximum subarray length $$$L_i$$$ where $$$a_i$$$ is the maximum.

So:

Compute $$$L_i$$$ for each element using stacks.

For each $$$L_i$$$, mark $$$a_i$$$ as available starting from subarray length $$$1$$$ up to $$$L_i$$$.

Sweep $$$k = 1 \dots n$$$, maintain which values appear, and compute the $$$\text{MEX}$$$ incrementally.

This runs in $$$O(n \log n)$$$ or $$$O(n)$$$ with careful implementation.

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

int main() {
	int n;
	cin >> n;
	vector<int> a (n);
	for (auto &x : a) cin >> x;
	vector<int> L (n, -1), R (n, n);
	stack<int> stk;
	for (int i = 0; i < n; i ++) {
		while (!stk.empty() && a[stk.top()] < a[i]) stk.pop();
		if (!stk.empty()) L[i] = stk.top();
		stk.push (i);
	}
	stk = stack<int>();
	for (int i = n - 1; i >= 0; i --) {
		while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
		if (!stk.empty()) R[i] = stk.top();
		stk.push (i);
	}
	vector<vector<int>> contrib (n + 1);
	for (int i = 0; i < n; i ++) {
		int len = R[i] - L[i] - 1;
		contrib[len].push_back (a[i]);
	}
	vector<bool> vis (n + 1, 0);
	int mex = 0;
	vector<int> ans (n + 1);
	for (int i = n; i >= 1; i --) {
		for (int x : contrib[i]) {
			if (x <= n && !vis[x]) {
				vis[x] = 1;
				while (vis[mex]) mex ++;
			}
		}
		ans[i] = mex;
	}
	for (int i = 1; i <= n; i ++) cout << ans[i] << " ";
	cout << "\n";
}

Consider how to add a single pennant.

First, you shift the groups to the right by 1 space, with 2 operations per group. Then you add your new pennant with 1 operation.

Example:

1 1 3 3 4 5 5 5 X
Adding a pennant of rank 2:
1 1 X 3 X X 5 5 X
1 1 X 3 3 4 5 5 5
1 1 2 3 3 4 5 5 5

Consider adding $$$a$$$ pennants of rank $$$k$$$. For each group with rank greater than $$$k$$$, you must shift it to the right by $$$a$$$ spaces. (You also need $$$a$$$ additional operations to actually put the new pennants on the wall.)

To shift a group with size $$$b$$$ to the right $$$a$$$ spots, either $$$b\le a$$$, so you move the entire group in $$$2b$$$ operations. Otherwise, it takes $$$2a$$$ operations to relocate $$$a$$$ pennants from the left border to the right border. Thus, for each group, you require $$$2\cdot \min(a, b)$$$ operations.

For the subtask, this can be calculated in $$$O(n^2)$$$ time.

To solve this in $$$O(n \log n)$$$ time, we can sweep from right to left, processing queries offline. We will maintain two arrays: $$$\mathrm{cnt}[i]$$$ denotes the number of groups on the right of size $$$i$$$, and $$$\mathrm{sum}[i] = i \cdot \mathrm{cnt}[i]$$$. Then, the sum over groups of $$$\min(a, \textrm{size})$$$ is equal to $$$\sum_0^a \mathrm{sum}[i] + a \cdot \sum_{a+1}^n \mathrm{cnt}[i]$$$. We can compute these sums with a fenwick tree.

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

struct fenwick {
        int n;
        vector<int> t;
        fenwick(int n) : n(n), t(n) {}
        void add(int i, int x) {
                for(;i<n;i|=i+1)t[i]+=x;
        }
        int query(int i) {
                if(i>=n) i=n-1;
                int x=0;
                for(;~i;i=(i&(i+1))-1)x+=t[i];
                return x;
        }
};

int main()
{
        int n=in,q=in,l=in;
        vector<int> f(n);
        vector<int> a(n);for(auto&x:a)x=in,x--,f[x]++;

        vector<vector<array<int,2>>> qs(n);
        for(int i=0;i<q;i++) {
                int a=in,k=in;k--;qs[k].push_back({i,a});
        }

        fenwick ft(n), ft2(n);
        vector<int> ans(n);

        for(int i=n-1;~i;i--) {
                for(auto [id, a] : qs[i]) {
                        ans[id] += a;
                        ans[id] += ft.query(a-1) * 2;
                        ans[id] += a * (n-i-1-ft2.query(a-1)) * 2;
                }
                ft.add(f[i],f[i]);
                ft2.add(f[i],1);
        }

        for(auto x:ans)
                printf("%d\n",x);
}

For each word, consider the players as a bitmask.

When is it possible to have any team?

Consider the bitmasks of two words $$$a$$$ and $$$b$$$. If $$$a \,|\, b = \underbrace{111\dots11_2}_{n\text{ times}}$$$, then it is possible to have two teams with words $$$a$$$ and $$$b$$$.

There is an edge case, which happens when there is a word such that all players may have it.

Let us consider the case where the edge case in hint 3 does not appear.

First, we consider each word as a bitmask $$$w_{i,j}$$$, where $$$w_{i,j} = 1$$$ if and only if player $$$j$$$ can possibly have word $$$i$$$. Clearly, it is possible to have a team when there are two words $$$a$$$, $$$b$$$, with $$$w_a \,|\, w_b = \underbrace{111\dots11_2}_{n\text{ times}}$$$. If the two words are unique, then $$$w_a$$$ must also be the complement of $$$w_b$$$.

Using a map, we can count the number of pairs $$$(a, b)$$$ which satisfy the above condition, such that $$$w_a$$$ is the compliment of $$$w_b$$$. If there is more than one pair, the answer is NO.

The only other way for the teams to be non-unique is if two words satisfy $$$w_a \,|\, w_b = \underbrace{111\dots11_2}_{n\text{ times}}$$$, but they are not complements of each other. Then, they must have at least one bit in common.

We can run a bitmask dp with $$$\mathrm{dp}[m] = 1$$$ if and only if there is a word with a submask equal to $$$m$$$. The transitions are standard. Then, we can iterate over all word masks, and for each word, we iterate over all common bits $$$j$$$. Then, we can query $$$\sim w_a \oplus 2^j$$$ in the dp ($$$\sim$$$ is not, $$$\oplus$$$ is xor), because if there is a word with submask equal to $$$\sim w_a\oplus 2^j$$$, then the words must share common bit $$$j$$$, so the answer is NO.

In all other cases, if there exists a possible configuration of teams, the answer is YES.

For the edge case in hint 3, it is only possible to have a unique team if there is only one player who claims another word, and that word is unique (see below case):

$$$ w_0 = 0001 $$$

$$$ w_1 = 1001 $$$

$$$ w_2 = 0001 $$$

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

int main()
{
        int tt=in;
        for(int ttn=0;ttn<tt;ttn++)
        {
                int n=in,m=in;
                vector<int> a(m);
                for(int i=0;i<n;i++) for(int j=0;j<m;j++) a[j]|=(char(in)-'0')<<i;

                ll ok=0;
                int sol1=0, sol2=0;

                int tot = 0;
                for(int i=0;i<m;i++)tot+=__builtin_popcount(a[i]);
                for(int i=0;i<m;i++) {
                        if(a[i] == (1<<n)-1) {
                                if(tot == n+1)
                                        for(int j=0;j<m;j++)if(j!=i&&a[j]) { sol1=i; sol2=j; goto yes; }
                                goto no;
                        }
                }
                {
                        map<int,int> mp,oc;for(int i=0;i<m;i++)mp[a[i]]=i,oc[a[i]]++;
                        for(int i=0;i<m;i++) {
                                int b = ((1<<n)-1) & ~a[i];
                                if(auto it=mp.find(b);it!=mp.end()&&it->first==b) {
                                //cout<<bitset<20>(a[i])<<' '<<bitset<20>(a[it->second])<<endl;
                                        ok+=oc[it->first];sol1=i;sol2=it->second;
                                }
                        }
                        if(ok!=2) goto no;
                        vector<int> dp(1<<n);for(auto x:a)dp[x]=1;
                        for(int i=(1<<n)-1;~i;i--) {
                                for(int j=0;j<n;j++)if(i>>j&1) {
                                        dp[i^(1<<j)]|=dp[i];
                                }
                        }
                        for(auto x:a) {
                                for(int j=0;j<n;j++)if(x>>j&1) {
                                        int z = ((1<<n)-1)^x^(1<<j);
                                        if(dp[z]) goto no;
                                }
                        }
                }

                //printf("ok=%d\n",ok);
                if(ok == 2) {yes:
                        printf("Yes\n");
                        if(sol1>sol2)swap(sol1,sol2);
                        printf("%d %d\n", sol1+1, sol2+1);
                }
                else no:printf("No\n");
                //printf("ok=%d\n",ok);
        }
}

Think non-simple paths, especially the ones that use the same edge several times.

Because a path does not need to be simple, at any node $$$u$$$, we can traverse the same edge twice in a row and return to $$$u$$$. Because of this, if we consider some path from $$$s$$$ to $$$t$$$ with path weight $$$c$$$, we can always augment the path weight by $$$2 \cdot w_i$$$ arbitrarily.

Let $$$g = \gcd(w_1, w_2, \dots, w_n)$$$. Then, using the ideas of Bezout's identity and the previous observation, all path weights in the set $$$\{c, 2g + c, \dots, 2(k-1) \cdot g + c\} \mod k$$$ are obtainable. Since $$$c \mid g$$$, only $$$c = 0$$$ and $$$c = g$$$ are important given they may form different sets.

If both $$$c$$$ values are obtainable, then the obtainable set of path weights is $$$\{0, g, \dots, g(k-1)\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, g)}$$$.

If only one $$$c$$$ is obtainable, the obtainable set of path weights is $$$\{c, 2g + c, \dots, 2(k-1)g + c\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, 2g)}$$$.

Define $$$W_i = \frac{w_i}{g}$$$. Let $$$W_i$$$ be the weights of a new graph. In this graph, we notice that the existence of an even path weight corresponds to $$$c = 0$$$ and the existence of an odd path weight corresponds to $$$c = g$$$. Calculating whether an odd and/or even path exists can be done using a BFS/DFS with two states per node $$$u$$$ (whether an odd/even path exists from $$$s$$$ to $$$u$$$), solving the problem in $$$\mathcal{O}(n)$$$.

If $$$g = 0$$$, then the answer is $$$1$$$. This must be handled manually to avoid division by $$$0$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n, m, qq, a, b;
ll k;
void solve() {
    cin >> n >> m >> k >> a >> b;
    a--, b--;
    ll g = 0;
    vector<pair<pi, ll>> edges(m);
    vector<vector<pi>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        edges[i] = {{--u, --v}, w};
        g = gcd(g, w);
    }

    if (g == 0) {
        cout << "1\n";
        return;
    }

    for (int i = 0; i < m; i++) {
        auto [p, w] = edges[i];
        auto [u, v] = p;
        adj[u].push_back({v, (w / g) & 1});
        adj[v].push_back({u, (w / g) & 1});
    }

    vector<vector<bool>> vis(2, vector<bool>(n));
    vis[0][a] = 1;
    queue<pi> q;
    q.push({0, a});
    while (!q.empty()) {
        auto [p, u] = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) {
            if (!vis[(p + w) & 1][v]) {
                vis[(p + w) & 1][v] = 1;
                q.push({(p + w) & 1, v});
            }
        }
    }

    if (!vis[0][b] || !vis[1][b]) g *= 2;
    cout << k / gcd(g, k) << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

$$$|a-b| = \max(a-b,b-a)$$$

Lets call John's nodes red and Nhoj's nodes black.

First, we can run Dijkstra's from node $$$1$$$ and node $$$2n$$$, to find the distances to every node. Let us denote these distances as $$$d_i$$$.

We wish to find the minimum value of $$$d_i + |x_i-x_j| + |y_i-y_j| + d_j$$$ for all red nodes $$$i$$$ and black nodes $$$j$$$.

Let's suppose that $$$x_i \lt x_j$$$ and $$$y_i \lt y_j$$$. Then, the above reduces to $$$(d_i-x_i-y_i)+(d_j+x_j+y_j)$$$. We can compute the minimum value of this by sweeping in the positive x direction, and using a point update / range minimum query segment tree. For all red nodes, we add the left side of the expression to the segment tree at index $$$y_i$$$. For all blue nodes, we query the segment tree for the minimum value at index $$$\le y_j$$$, and add it to the right side of the expression.

To do this for the other cases, we can rotate the grid by 90 degrees, and then run the above algorithm again. Do note that we need either a sparse segtree or coordinate compression, both should pass comfortably.

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

#define N 200000
#define NN N*40
#define X int(1e9)

ll val[NN]; int lc[NN], rc[NN];
int vv=2;

#define vm (vl+(vr-vl)/2)
void update(int i, ll x, int& v, int vl, int vr) {
        if(v==0)v=vv++;
        val[v]=min(val[v],x);
        if(vl==vr) return;
        i<=vm?update(i,x,lc[v],vl,vm):update(i,x,rc[v],vm+1,vr);
}
ll query(int l, int r, int v, int vl, int vr) {
        if(l==vl&&r==vr) return val[v];
        if(r<=vm)return query(l,r,lc[v],vl,vm);
        else if(l>vm)return query(l,r,rc[v],vm+1,vr);
        else return min(query(l,vm,lc[v],vl,vm),query(vm+1,r,rc[v],vm+1,vr));
}

int main()
{
        int n=in,m=in;

        vector<array<int,2>> pos(2*n);for(auto&[x,y]:pos)x=in,y=in;

        vector<vector<array<int,2>>> adj(2*n);
        while(m--) {
                int u=in,v=in;u--;v--;int e=in;
                adj[u].push_back({v,e});
                adj[v].push_back({u,e});
        }

        priority_queue<array<ll,2>> pq;
        vector<ll> dist(2*n,infl);
        dist[0]=dist[2*n-1]=0;
        pq.push({-0,0});
        pq.push({-0,2*n-1});
        while(pq.size()) {
                auto [d,v]=pq.top();pq.pop();d=-d;
                if(d>dist[v])continue;

                for(auto [x,w]:adj[v]) {
                        if(d+w<dist[x]) {
                                dist[x]=d+w;
                                pq.push({-d-w,x});
                        }
                }
        }

        ll ans=infl;
        for(int it=0;it<4;it++) {
                for(int i=0;i<2*n;i++) {
                        tie(pos[i][0], pos[i][1]) = make_pair(pos[i][1], X-pos[i][0]);
                }
                memset(val,0x3f,sizeof(val));
                memset(lc,0,sizeof(lc));
                memset(rc,0,sizeof(rc));
                vv = 2;

                int rt = 1;
                vector<int> a(2*n);for(int i=0;i<2*n;i++)a[i]=i;
                sort(all(a),[&](auto u, auto v) {
                        return pos[u][0]<pos[v][0];
                });

                for(auto i:a) {
                        if(i<n) update(pos[i][1],dist[i]-pos[i][0]-pos[i][1],rt,0,X);
                        if(i>=n) ans=min(ans,query(0,pos[i][1],rt,0,X)+dist[i]+pos[i][0]+pos[i][1]);
                }
        }
        //for(int i=0;i<n;i++) {
                //for(int j=n;j<2*n;j++) {
                        //ans=min(ans,dist[i]+dist[j]+abs(pos[i][0]-pos[j][0])+abs(pos[i][1]-pos[j][1]));
                //}
        //}
        printf("%lld\n",ans);
}

Formulate a DP.

Dijkstra?

Let's solve this using DP. Let $$$d_{i, j}$$$ be the minimum number of robots required to get one robot on cell $$$(i, j)$$$. At the start, if cell $$$(i, j)$$$ is a spawn point $$$A$$$, then $$$d_{i, j} = 1$$$, otherwise $$$d_{i, j} = \text{INF} = 4 \cdot 10^{18} + 1$$$ to denote that $$$(i, j)$$$ is unreachable.

Let $$$x$$$ be some cell $$$(i, j)$$$ and $$$y$$$ be some cell orthogonally adjacent to $$$x$$$. If $$$d_x, d_y \neq \text{INF}$$$, then the robot in $$$x$$$ can push the robot in $$$y$$$ to cell $$$z$$$ (if cell $$$z$$$ is not an obstacle), setting $$$d_z$$$ to $$$\min(d_z, d_x + d_y)$$$.

Since there is no proper order to process the states, naively looping through the grid $$$nm$$$ times to calculate the states takes $$$\mathcal{O}(n^2m^2)$$$ computations. Although there is no graph nor specific edge weights, Dijkstra's algorithm can be used here. What Dijkstra does is order and process the states in non-decreasing $$$d_{i, j}$$$, eliminating wasted computations. Note that when processing cell $$$x$$$, for some orthogonally adjacent $$$y$$$, both $$$x$$$ pushing $$$y$$$ and $$$y$$$ pushing $$$x$$$ must be considered, for a total of $$$8$$$ transitions per cell. This solves the problem in $$$\mathcal{O}(nm \log nm)$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

const int N = 1005;
const ll inf = (ll)4e18 + 1;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
char grid[N][N];
ll dist[N][N];
int n, m, k, qq;
void solve() {
    cin >> n >> m;
    int tx, ty;
    priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'A') {
                dist[i][j] = 1;
                q.push({1, {i, j}});
            }

            else dist[i][j] = inf;
            if (grid[i][j] == 'B') tx = i, ty = j;
        }
    }

    auto ok = [&](int x, int y) {
        return (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#');
    };

    while (!q.empty()) {
        auto [d, p] = q.top();
        auto [x, y] = p;
        q.pop();
        if (d != dist[x][y]) continue;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!ok(nx, ny)) continue;
            ll nd = d + dist[nx][ny];
            nx += dx[i], ny += dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }

            nx = x - dx[i], ny = y - dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }
        }
    }

    cout << (dist[tx][ty] == inf ? -1 : dist[tx][ty]) << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

How do you solve the distinct element case?

How many nice intervals are there?

For the remainder of the problem, we assume zero-indexing, and we subtract $$$1$$$ from every element in the array.

Consider how to solve the problem for a single query. The problem reduces to choosing a prefix of the array, then the answer is $$$\max(a_l,a_{l+1},\dots,a_r) - (r-l)$$$.

Let's define a nice interval as an interval without any duplicate elements, and a really nice interval as a nice interval that cannot be extended left or right without either introducing duplicate elements or changing the maximum element.

In the distinct elements case, every interval is nice. Also, each node corresponds to a really nice interval, which extends left until the next highest element, and similarly to the right.

For the non-distinct elements case, we will figure it out later.

We can now describe how to solve a single case using really nice intervals. Note that for a query, either you take the entire array (and it is nice), or you take a prefix. In the latter case, it is always optimal to take a prefix that cannot be extended to the right without either introducing duplicate elements, or increasing the maximum. In all other cases, extending the prefix to the right will decrease the answer by 1. Notice that this is exactly the suffix of a really nice interval!

It is useful to maintain 2 RMQs (I used sparse table). For the first RMQ, we store the elements in the array, so we can find the maximum of any interval. For the second RMQ, we store index of the previous occurrence of every element, so that we can determine whether a subarray is nice (that is, it has no duplicate elements).

Now, we can answer each query offline. Consider sweeping left to right, processing intervals and queries at their left endpoint. We maintain a segment tree that can maintain point updates and range minimum queries. At each really nice interval, we update $$$\mathrm{mx} - r$$$ at the right endpoint in the segment tree. At each query, we query the segment tree between $$$l$$$ and $$$r$$$, and add $$$l$$$ to the answer. We also compare this to the answer if we take the entire interval of the query (we can find this using our 2 RMQs).

Now it remains to find the really nice intervals for general arrays, with possibly non-distinct elements. For each element, consider the interval formed by extending left until a larger element or a duplicate with another element on the left, and similarly right until a larger element or a duplicate with another element on the right ( not on the left ). If this interval is nice, then it must also be really nice. Otherwise, there must be at least one pair of duplicate elements, and all really nice intervals containing the same maximum element must stop at one end of one such pair of duplicate elements.

Without loss of generality, fix one of the pairs, which we will denote as $$$(i,j)$$$. Consider the interval that consists of the subarray between $$$k$$$ and $$$j-1$$$, where $$$k$$$ is the minimum possible such that this interval is nice and has the same maximum element as the subarray between $$$i$$$ and $$$j$$$. Then, this interval must be really nice. To find all such intervals, we can consider each $$$k$$$ from $$$1\dots n$$$, and binary search to extend this interval as far right as possible. The same applies in reverse (extending to the left).

Thus, there are at most $$$3\cdot n$$$ really nice intervals, and we can compute them using binary search and our 2 RMQ's in $$$O(n \log n)$$$ time. Thus, our entire solution runs in $$$O(n \log n)$$$ time.

#line 1 "full.cpp"
// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#line 15 "full.cpp"
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

#line 2 "/home/jayjay/dev2/comp/lib/ds/rmq.hpp"

#line 5 "/home/jayjay/dev2/comp/lib/ds/rmq.hpp"
using namespace std;

template<typename T, int LG=20, typename Compare = less<T>>
struct RMQ {
        int n;
        vector<T> arr;
        vector<int> st;
        RMQ(int n) : n(n), arr(n), st(n*LG) {
                assert(n <= 1<<LG);
                for(int i=0;i<n;i++) st[i] = i;
        }
        int argmin(int a, int b) {
                return Compare()(arr[a],arr[b]) ? a : b;
        }
        template<typename Tp>
        void build(Tp a) {
                for(int i=0;i<n;i++) arr[i] = a[i];
                for(int l=1; l<LG; l++)
                        for(int i=0; i + (1<<(l-1)) < n; i++)
                                st[l*n+i] = argmin(
                                                st[(l-1)*n + i],
                                                st[(l-1)*n + i + (1<<(l-1))]);
        }
        int query(int l, int r) {
                r++;
                int k = __lg(r - l);
                return argmin(st[k*n + l], st[k*n + r - (1<<k)]);
        }
};
#line 2 "/home/jayjay/dev2/comp/lib/ds/isegtree.hpp"

#line 1 "/home/jayjay/dev2/comp/lib/func.hpp"
struct func_add {
        template<typename T>
        T operator()(T a, T b) const {
                return a + b;
        }
};
struct func_min {
        template<typename T>
        T operator()(T a, T b) const {
                return min(a, b);
        }
};
struct func_max {
        template<typename T>
        T operator()(T a, T b) const {
                return max(a, b);
        }
};
#line 4 "/home/jayjay/dev2/comp/lib/ds/isegtree.hpp"

template<typename T=long long, typename oper=func_add, T id={}>
struct isegtree // oper should be: associative, has identity
{
        int n; std::vector<T> t;

        isegtree(int n) : n(n), t(2*n-1, id) {}
        isegtree() : isegtree(1) {}

        void resize(int n) { // UB if tree is nonzero
                this->n=n;
                t.resize(2*n-1);
        }

        template<typename Tp>
        void build(Tp a) {
                for(int i=n-1;~i;i--) t[i+n-1] = a[i];
                for(int i=n-2;~i;i--) t[i] = oper()(t[i*2+1], t[i*2+2]);
        }

        void update(int i, T x) {
                i += n-1;
                t[i] = x;
                while(i > 0) i = (i-1)/2, t[i] = oper()(t[i*2+1], t[i*2+2]);
        }

        T query(int l, int r) {
                l += n-1; r += n-1;
                T lans = id, rans = id;
                while(l < r) {
                        if(~l&1) lans = oper()(lans, t[l++]);
                        if(r&1)  rans = oper()(t[r--], rans);
                        l = (l-1) / 2;
                        r = (r-1) / 2;
                }
                if(l == r) return oper()(oper()(lans, t[l]), rans);
                else return oper()(lans, rans);
        }
};
#line 28 "full.cpp"

int main()
{
        int n=in, q=in;vector<int> a(n);for(auto&x:a)x=in,x--;

        vector<int> prev(n);
        map<int,int> pr;
        for(int i=0;i<n;i++) {
                if(pr.count(a[i])==0)prev[i] = -1;
                else prev[i] = pr[a[i]];
                pr[a[i]] = i;
        }

        RMQ<int, 20, greater<int>> rmq(n); rmq.build(a);
        RMQ<int, 20, greater<int>> pm(n);pm.build(prev);
        //for(int i=0;i<n;i++)printf("%d ",prev[i]);
        //printf("\n");
        auto isnice = [&](int l, int r) {
                //printf("isnice %d %d = %d\n",l,r,pm.query(l,r)<l);
                return prev[pm.query(l,r)] < l;
        };

        vector<int> nl(n), nr(n);
        {
                vector<int> stk;
                for(int i=0;i<n;i++) {
                        while(stk.size() && a[stk.back()] < a[i]) stk.pop_back();
                        nl[i] = stk.size()?stk.back():-1;
                        stk.push_back(i);
                }
        }
        {
                vector<int> stk;
                for(int i=n-1;~i;i--) {
                        while(stk.size() && a[stk.back()] < a[i]) stk.pop_back();
                        nr[i] = stk.size()?stk.back():n;
                        stk.push_back(i);
                }
        }

        vector<vector<array<int,2>>> nice(n);
        for(int i=0;i<n;i++) {
                int l = nl[i]+1, r = nr[i]-1;
                if(isnice(l, r))
                        nice[l].push_back({r, a[rmq.query(l,r)]});
        }
        for(int i=0;i<n;i++) {
                int l=i,r=n-1;
                while(l<r) {
                        int m = l+(r-l+1)/2;
                        if(isnice(i,m))l=m;
                        else r=m-1;
                }
                nice[i].push_back({r,a[rmq.query(i,r)]});
        }
        for(int i=0;i<n;i++) {
                int l=0, r=i;
                while(l<r) {
                        int m = l+(r-l)/2;
                        if(isnice(m,i))r=m;
                        else l=m+1;
                }
                nice[l].push_back({i,a[rmq.query(l,i)]});
        }
        //for(int i=0;i<n;i++)for(auto [r,m]:nice[i])printf("nice %d %d %d\n",i,r,m);

        vector<int> ans(q);
        vector<vector<array<int,2>>> qs(n);
        for(int i=0;i<q;i++) {
                int l=in,r=in; l--;r--;qs[l].push_back({r,i});
        }

        isegtree<int,func_min,inf> st(n);

        for(int i=0;i<n;i++) {
                for(auto [r, mx] : nice[i]) {
                        st.update(r,mx-r);
                }

                for(auto [r, id] : qs[i]) {
                        ans[id] = st.query(i, r) + i;
                        if(isnice(i,r)) ans[id] = min(ans[id], a[rmq.query(i,r)] - r + i);
                        //printf("id=%d: %d + %d  ||  %d - %d + %d\n",id, st.query(i,r),i,a[rmq.query(i,r)],r,i);
                }
        }

        for(auto x:ans) printf("%d\n", x);
}

Look for invariants

Observation 1: Let white stones represent $$$+1$$$, and black stones represent $$$-1$$$. The difference between the values of two people's stones is constant. If the starting value of stones is $$$a_i$$$, then the ending value will be $$$a_i + C$$$, for some constant $$$C$$$.

Observation 2: Define a pair of stones to be a black stone and a white stone. Note that these pairs can be freely moved. BW,0,0 B,B,B 0,0,BW

Observation 3: If there are $$$N-2$$$ pairs, and one extra stone, they can be eliminated BW, BW, BW, B, 0 W, W, W, 0, W 0, 0, 0, B, 0

Observation 4: If there are less than $$$N-2$$$ pairs, they cannot be removed without changing $$$C$$$. Proof: Every operation changes $$$C$$$ by $$$1$$$. Thus, to not change $$$C$$$, you must perform an even number of operations. Since the total number of stones changes by $$$N-2$$$ each operation, after an even number of operations, thus changing the total number of stones by a multiple of $$$2(N-2)$$$.

Thus, for a given $$$C$$$, the minimum number of pairs can be computed. It can be shown, that the value of $$$C$$$ that minimizes the stones is the negative of the median of $$$a_i$$$, plus or minus 1. Thus, you can simply test those values.

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


ll n;
ll a [1005000];
ll w [1005000];
ll b [1005000];

ll tot = 0;
ll tmodev = 0;
ll tmodod = 0;

ll firstGeq(ll x, ll m, ll mod){//first number at least x that is m mod mod
    if(x == 0 && m == 0){
        return mod;
    }
    if(x%mod <= m){
        return (x/mod * mod) + m;
    }else{
        return ((x/mod + 1) * mod) + m;
    }
}

ll getCMin(ll c){
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans += max(a[i] - c, c - a[i]);
    }
    if(c%2 == 0){
        return firstGeq(ans, tmodev, 2 * (n - 2));
    }else{
        return firstGeq(ans, tmodod, 2 * (n - 2));
    }
}

void solve(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    for(int i = 0; i < n; i++){
        cin >> w[i];
    }

    tot = 0;
    for(int i = 0; i < n; i++){
        a[i] = w[i] - b[i];
        tot += (w[i] + b[i]);
    }
    tmodev = (tot)%(2*(n-2));
    tmodod = (tot + (n-2))%(2*(n-2));
    sort(a, a+n);
    if(tot == 0){
        cout << 0 << endl;
    }else{
        ll ans = (1ll << 60);
        for(int i = n/2; i <= (n/2+1); i++){
            for(int j = -1; j <= 1; j++){
                ans = min(ans, getCMin(a[i] + j));
            }
        }
        cout << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for(int tc = 0; tc < t; tc++){
        solve();
    }
}

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const bool DEBUG=false;
struct Return{
    ll ans;
    vector<int>ord[2][2][2];// prefix/suffix, 0/min, 0/max
    Return(int i){
        ans=1;
        for(int a=0;a<8;++a)ord[a>>2][(a>>1)&1][a&1]={i};
    }
    Return(int initialAns,int vsize){
        ans=initialAns;
        for(int a=0;a<8;++a)ord[a>>2][(a>>1)&1][a&1].reserve(vsize);
    }
};

int n;
vector<int>arr,disc,cnt,mergeBuf[5];
vector<int>prefOpt[2][2];
vector<array<int,2>>halfOpt;
int infected[2][2];

template<typename Func1,typename Func2>
int mergeSort(vector<int>&bufLeft,vector<int>&bufRight,Func1&&evalLeft,Func2&&evalRight){
    int m=bufRight.size();
    int ptrLeft=0,ptrRight=m-1;
    int lstLeft=evalLeft(bufLeft[0]),lstRight=evalRight(bufRight[m-1]),lst=INT_MAX;
    int h=-1;
    while(true){
        if(lstLeft<lstRight){
            if(lst!=lstLeft)++h,lst=lstLeft;
            disc[bufLeft[ptrLeft]]=h;
            ++ptrLeft;
            if(ptrLeft<bufLeft.size())lstLeft=evalLeft(bufLeft[ptrLeft]);
            else break;
        }
        else{
            if(lst!=lstRight)++h,lst=lstRight;
            disc[bufRight[ptrRight]]=h;
            --ptrRight;
            if(ptrRight>=0)lstRight=evalRight(bufRight[ptrRight]);
            else break;
        }
    }
    while(ptrLeft<bufLeft.size()){
        lstLeft=evalLeft(bufLeft[ptrLeft]);
        if(lst!=lstLeft)++h,lst=lstLeft;
        disc[bufLeft[ptrLeft]]=h;
        ++ptrLeft;
    }
    while(ptrRight>=0){
        lstRight=evalRight(bufRight[ptrRight]);
        if(lst!=lstRight)++h,lst=lstRight;
        disc[bufRight[ptrRight]]=h;
        --ptrRight;
    }
    return h+1;
}

template<typename Func>
void mergeSort(vector<int>&bufLeft,vector<int>&bufRight,Func&&eval,vector<int>&outBuf){
    if(bufLeft.empty())return outBuf.swap(bufRight);
    if(bufRight.empty())return outBuf.swap(bufLeft);
    int ptrLeft=0,ptrRight=0;
    while(ptrLeft<bufLeft.size()&&ptrRight<bufRight.size())
        outBuf.push_back(eval(bufLeft[ptrLeft])<eval(bufRight[ptrRight])?bufLeft[ptrLeft++]:bufRight[ptrRight++]);
    while(ptrLeft<bufLeft.size())outBuf.push_back(bufLeft[ptrLeft++]);
    while(ptrRight<bufRight.size())outBuf.push_back(bufRight[ptrRight++]);
}

using Func=int(*)(int);
static const Func eval[8]={
    [](int i)->int{return arr[i]-0-0;},
    [](int i)->int{return arr[i]-0-prefOpt[0][1][i];},
    [](int i)->int{return arr[i]-prefOpt[0][0][i]-0;},
    [](int i)->int{return arr[i]-prefOpt[0][0][i]-prefOpt[0][1][i];},
    [](int i)->int{return arr[i]-0-0;},
    [](int i)->int{return arr[i]-0-prefOpt[1][1][i];},
    [](int i)->int{return arr[i]-prefOpt[1][0][i]-0;},
    [](int i)->int{return arr[i]-prefOpt[1][0][i]-prefOpt[1][1][i];}
};
Return dnq(int l,int r){
    if(r-l<=16){
        Return ret(0,r-l+1);
        prefOpt[0][0][l-1]=prefOpt[1][0][r+1]=inf,prefOpt[0][1][l-1]=prefOpt[1][1][r+1]=-inf;
        for(int a=l;a<=r;++a)prefOpt[0][0][a]=min(prefOpt[0][0][a-1],arr[a]),prefOpt[0][1][a]=max(prefOpt[0][1][a-1],arr[a]);
        for(int a=r;a>=l;--a)prefOpt[1][0][a]=min(prefOpt[1][0][a+1],arr[a]),prefOpt[1][1][a]=max(prefOpt[1][1][a+1],arr[a]);
        for(int a=0;a<8;++a){
            auto&v=ret.ord[a>>2][(a>>1)&1][a&1];
            v.resize(r-l+1);
            iota(v.begin(),v.end(),l);
            sort(v.begin(),v.end(),[&](int i,int j){
                return eval[a](i)<eval[a](j);
            });
        }
        for(int a=l;a<=r;++a){
            int accuMin=inf,accuMax=-inf;
            for(int b=a;b<=r;++b){
                accuMin=min(accuMin,arr[b]);
                accuMax=max(accuMax,arr[b]);
                ret.ans+=(accuMin+accuMax==arr[a]+arr[b]);
            }
        }
        return ret;
    }
    int mid=(l+r)/2;
    auto lres=dnq(l,mid);
    auto rres=dnq(mid+1,r);
    ll subAns=lres.ans+rres.ans;
    for(int a=mid,accuMin=inf,accuMax=-inf;a>=l;--a)halfOpt[a]={accuMin=min(accuMin,arr[a]),accuMax=max(accuMax,arr[a])};
    for(int a=mid+1,accuMin=inf,accuMax=-inf;a<=r;++a)halfOpt[a]={accuMin=min(accuMin,arr[a]),accuMax=max(accuMax,arr[a])};
    {
        static const Func halfEval[8]={
            [](int i)->int{return arr[i]-0-0;},
            [](int i)->int{return arr[i]-0-halfOpt[i][1];},
            [](int i)->int{return arr[i]-halfOpt[i][0]-0;},
            [](int i)->int{return arr[i]-halfOpt[i][0]-halfOpt[i][1];},
            [](int i)->int{return -(arr[i]-0-0);},
            [](int i)->int{return -(arr[i]-0-halfOpt[i][1]);},
            [](int i)->int{return -(arr[i]-halfOpt[i][0]-0);},
            [](int i)->int{return -(arr[i]-halfOpt[i][0]-halfOpt[i][1]);}
        }; 
        #pragma unroll
        for(int leftMask=0;leftMask<4;++leftMask){
            int rightMask=(3^leftMask);
            mergeSort(lres.ord[1][leftMask>>1][leftMask&1],rres.ord[0][rightMask>>1][rightMask&1],halfEval[0|leftMask],halfEval[4|rightMask]); 
            fill(cnt.begin(),cnt.begin()+r-l+1,0);
            int minRp=mid+1,maxRp=mid;
            for(int lp=mid;lp>=l;--lp){
                while(maxRp+1<=r&&(!(leftMask&2)||(halfOpt[maxRp+1][0]>=halfOpt[lp][0]))&&(!(leftMask&1)||(halfOpt[maxRp+1][1]<=halfOpt[lp][1])))++cnt[disc[++maxRp]];
                while(minRp<=maxRp&&(((rightMask&2)&&(halfOpt[minRp][0]>=halfOpt[lp][0]))||((rightMask&1)&&(halfOpt[minRp][1]<=halfOpt[lp][1]))))--cnt[disc[minRp++]];
                subAns+=cnt[disc[lp]];
            }
        }
    }
    Return res(subAns,r-l+1);
    prefOpt[0][0][l-1]=prefOpt[1][0][r+1]=inf,prefOpt[0][1][l-1]=prefOpt[1][1][r+1]=-inf;
    for(int a=l;a<=r;++a)prefOpt[0][0][a]=min(prefOpt[0][0][a-1],arr[a]),prefOpt[0][1][a]=max(prefOpt[0][1][a-1],arr[a]);
    for(int a=r;a>=l;--a)prefOpt[1][0][a]=min(prefOpt[1][0][a+1],arr[a]),prefOpt[1][1][a]=max(prefOpt[1][1][a+1],arr[a]);
    if(r-l+1!=n){
        mergeSort(lres.ord[0][0][0],rres.ord[0][0][0],eval[0],res.ord[0][0][0]);
        res.ord[1][0][0]=res.ord[0][0][0];
        infected[0][0]=infected[0][1]=r+1;
        infected[1][0]=infected[1][1]=l-1;
        for(int mnmx:{0,1})
            for(int a=mid+1;a<=r;++a)
                if(prefOpt[0][mnmx][a]!=prefOpt[0][mnmx][mid]){
                    infected[0][mnmx]=a;
                    break;
                }
        for(int mnmx:{0,1})
            for(int a=mid;a>=l;--a)
                if(prefOpt[1][mnmx][a]!=prefOpt[1][mnmx][mid]){
                    infected[1][mnmx]=a;
                    break;
                }
        struct Range{
            int lo,hi,mask;
        };
        //Left
        #pragma unroll
        for(int mn:{0,1}){
            #pragma unroll
            for(int mx:{0,1}){
                if(!mn&&!mx)continue;
                static Range ran[3];
                int h=0,bufh=0;
                if(infected[0][0]<=infected[0][1]){
                    if(mid+1<infected[0][0])ran[h++]={mid+1,infected[0][0]-1,0};
                    if(infected[0][0]<infected[0][1])ran[h++]={infected[0][0],infected[0][1]-1,mn<<1};
                    if(infected[0][1]<=r)ran[h++]={infected[0][1],r,mn<<1|mx};
                }
                else{
                    if(mid+1<infected[0][1])ran[h++]={mid+1,infected[0][1]-1,0};
                    if(infected[0][1]<infected[0][0])ran[h++]={infected[0][1],infected[0][0]-1,mx};
                    if(infected[0][0]<=r)ran[h++]={infected[0][0],r,mn<<1|mx};
                }
                for(int i=0;i<h;){
                    int j=i,lo=ran[i].lo,hi=ran[i].hi;
                    while(j<h&&ran[j].mask==ran[i].mask)hi=ran[j++].hi;
                    for(int k:rres.ord[0][(ran[i].mask>>1)&1][ran[i].mask&1])if(lo<=k&&k<=hi)mergeBuf[bufh].push_back(k);
                    i=j,++bufh;
                }
                assert(!mergeBuf[0].empty());
                if(lres.ord[0][mn][mx].size()>mergeBuf[1].size()+mergeBuf[2].size()){
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[0|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[0],mergeBuf[3],eval[0|mn<<1|mx],mergeBuf[4]);
                    mergeSort(lres.ord[0][mn][mx],mergeBuf[4],eval[0|mn<<1|mx],res.ord[0][mn][mx]);
                }
                else{
                    mergeSort(lres.ord[0][mn][mx],mergeBuf[0],eval[0|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[0|mn<<1|mx],mergeBuf[4]);
                    mergeSort(mergeBuf[3],mergeBuf[4],eval[0|mn<<1|mx],res.ord[0][mn][mx]);
                }
                for(int x=0;x<5;++x)mergeBuf[x].clear();
            }
        }
        //Right
        #pragma unroll
        for(int mn:{0,1}){
            #pragma unroll
            for(int mx:{0,1}){
                if(!mn&&!mx)continue;
                static Range ran[3];
                int h=0,bufh=0;
                if(infected[1][0]>=infected[1][1]){
                    if(mid>infected[1][0])ran[h++]={infected[1][0]+1,mid,0};
                    if(infected[1][1]<infected[1][0])ran[h++]={infected[1][1]+1,infected[1][0],mn<<1};
                    if(l<=infected[1][1])ran[h++]={l,infected[1][1],mn<<1|mx};
                }
                else{
                    if(mid>infected[1][1])ran[h++]={infected[1][1]+1,mid,0};
                    if(infected[1][0]<infected[1][1])ran[h++]={infected[1][0]+1,infected[1][1],mx};
                    if(l<=infected[1][0])ran[h++]={l,infected[1][0],mn<<1|mx};
                }
                for(int i=0;i<h;){
                    int j=i,lo=ran[i].lo,hi=ran[i].hi;
                    while(j<h&&ran[j].mask==ran[i].mask)lo=ran[j++].lo;
                    for(int k:lres.ord[1][(ran[i].mask>>1)&1][ran[i].mask&1])if(lo<=k&&k<=hi)mergeBuf[bufh].push_back(k);
                    i=j,++bufh;
                }
                if(rres.ord[1][mn][mx].size()>mergeBuf[1].size()+mergeBuf[2].size()){
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[4|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[0],mergeBuf[3],eval[4|mn<<1|mx],mergeBuf[4]);
                    mergeSort(rres.ord[1][mn][mx],mergeBuf[4],eval[4|mn<<1|mx],res.ord[1][mn][mx]);
                }
                else{
                    mergeSort(rres.ord[1][mn][mx],mergeBuf[0],eval[4|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[4|mn<<1|mx],mergeBuf[4]);
                    mergeSort(mergeBuf[3],mergeBuf[4],eval[4|mn<<1|mx],res.ord[1][mn][mx]);
                }
                for(int x=0;x<5;++x)mergeBuf[x].clear();
            }
        }
    }
    return res;
}
signed main(){
    iostream::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    arr.resize(n+2),halfOpt.resize(n+2);
    for(int i=0;i<5;++i)mergeBuf[i].reserve(n);
    for(auto i:{&disc,&cnt,&prefOpt[0][0],&prefOpt[0][1],&prefOpt[1][0],&prefOpt[1][1]})i->resize(n+2);
    for(int a=1;a<=n;++a)cin>>arr[a];
    cout<<dnq(1,n).ans<<endl;
}

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

constexpr int HALF_SUM=2000000;
constexpr int K=65535;

int solve(vector<int> a){
    static array<uint32_t,K+1> freq;
    fill(freq.begin(),freq.end(),0);
    vector<int> v; v.reserve(a.size());
    for(int x: a){
        if (x<=K) ++freq[x];
        else v.push_back(x);
    }
    for(int i=1;i<=K>>1;++i){
        if(freq[i]==0) continue;
        freq[i<<1]+=(freq[i]-1)>>1;
        freq[i]=2-(freq[i]&1);
    }
    static bitset<HALF_SUM+1> bs;
    bs.reset(); bs.set(0);
    int S=0;
    for(int i=1;i<=K;++i){
        while(freq[i]--){
            S+=i;
            bs|=(bs<<i);
        }
    }
    for(int x: v){
        S+=x;
        bs|=(bs<<x);
    }
    for(int i=S>>1;i>=0;--i) if(bs[i]) return i;
}

static inline int read_int(){
    int c=_getchar_nolock();
    while(c<'0') c=_getchar_nolock();
    int x=0;
    while(c>='0'){
        x=x*10+(c-'0');
        c=_getchar_nolock();
    }
    return x;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    const int n=read_int();
    if(n==1){
        cout << "0\n";
        return 0;
    }
    vector<int> deg(n,0);
    vector<int> xr(n,0);
    vector<int> sz(n,1);
    vector<int> mx(n,0);
    for (int i=0;i<n-1;++i){
        int u=read_int()-1;
        int v=read_int()-1;
        ++deg[u]; ++deg[v];
        xr[u]^=v; xr[v]^=u;
    }
    for (int i=0;i<n;++i){
        int v=i;
        while(deg[v]==1){
            int p=xr[v];
            sz[p]+=sz[v];
            deg[v]=0;
            --deg[p];
            xr[p]^=v;
            v=p;
        }
    }
    int root=find(sz.begin(),sz.end(),n)-sz.begin();
    xr[root]=-1;
    for(int v=0;v<n;++v){
        if(v==root) continue;
        mx[xr[v]]=max(mx[xr[v]],sz[v]);
    }
    int centroid=0,best=n;
    for(int v=0;v<n;++v){
        int comp=n-sz[v];
        int worst=max(mx[v],comp);
        if(worst<best){best=worst;centroid=v;}
    }
    vector<int> sts;
    for(int v=0;v<n;++v) if(xr[v]==centroid) sts.push_back(sz[v]);
    if(centroid!=root) sts.push_back(n-sz[centroid]);
    long long total=0;
    for(int v=0;v<n;++v) total+=sz[v];
    if(centroid!=root){
        long long delta=0;
        delta+=(long long)n-sz[centroid];
        int child=centroid;
        int par=xr[child];
        long long down=sz[child];
        while(par!=-1){
            long long oldsiz=sz[par];
            long long newsiz=n-down;
            delta+=newsiz-oldsiz;
            down=oldsiz;
            child=par;
            par=xr[par];
        }
        total+=delta;
    }
    long long k=solve(sts);
    cout << total+k*(n-1-k) << '\n';
    return 0;
}