Let $$$y$$$ denote the final position of all of the slimes. Then it is optimal to choose $$$x = y$$$ for every operation.

Let $$$\mathrm{mn}$$$ denote the minimum value in $$$a$$$, and let $$$\mathrm{mx}$$$ denote the maximum value in $$$a$$$. Now, the number of operations that you need to apply is equal to $$$\max(y - \mathrm{mn}, \mathrm{mx} - y)$$$.

We want to choose the value of $$$y$$$ that minimizes $$$\max(y - \mathrm{mn}, \mathrm{mx} - y)$$$. Therefore, we will choose the value that is closest to the middle of $$$\mathrm{mn}$$$ and $$$\mathrm{mx}$$$. This yields a final answer of $$$\lceil \frac{\mathrm{mx} - \mathrm{mn}}{2} \rceil$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

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

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int mx = *max_element(a.begin(), a.end());
    int mn = *min_element(a.begin(), a.end());
    cout << (mx - mn + 1) / 2 << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Consider each index separately. For one of the indices, you will gain value equal to $$$a_i + b_i$$$. For all of the other indices, you will gain value equal to $$$b_i$$$ only.

It is never bad to put the larger value in $$$b_i$$$.

We should swap any $$$a_i$$$ where $$$a_i \gt b_i$$$, because we would prefer for the larger value to be in $$$b_i$$$. In total, we gain value equal to the maximums of each pair, plus the largest of the minimums of each pair.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

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

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    ll sum = 0;
    for (int i = 0; i < n; i++)
        sum += max(a[i], b[i]);

    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, sum + min(a[i], b[i]));
    
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Suppose you have a positive element. You can make this element negative without affecting any later elements by applying an operation onto it directly.

You can make all of the elements negative. To do so, consider each index starting from $$$n$$$ to $$$1$$$. If it is currently positive, you can apply an operation on this index, turning it negative.

Let $$$\mathrm{idx}$$$ be the largest index you ever operate on. Then since you can never flip its sign using an operation on a later index, $$$a_{\mathrm{idx}}$$$ must initially be positive, and it will be negative after performing the operation.

Read the hints. In fact, it is always possible to make all elements before $$$\mathrm{idx}$$$ positive. Thus, in the end you end up with either the original array (if you applied no operations), or an array of the form $$$[|a_1|, ..., |a_{\mathrm{idx}-1}|, -a_{\mathrm{idx}}, a_{\mathrm{idx}+1}, ..., a_n]$$$ for some $$$\mathrm{idx}$$$ where $$$a_{\mathrm{idx}}$$$ is initially positive. You can find the optimal choice of $$$\mathrm{idx}$$$ using prefix and suffix arrays.

To make all of the elements before $$$\mathrm{idx}$$$ positive, you can first make them all negative by applying the method in the easy version. Then at the end, you can perform an operation on $$$\mathrm{idx}$$$, yielding the optimal array.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

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

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int par = 0;
    vector<int> ans;
    for (int i = n - 1; i >= 0; i--){
        if (par == 1)
            a[i] = -a[i];
        if (a[i] > 0){
            ans.push_back(i);
            par ^= 1;
        }
    }

    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

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

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<ll> pre(n), suf(n + 1);
    pre[0] = abs(a[0]);
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + abs(a[i]);
    
    suf[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
        suf[i] = suf[i + 1] + a[i];

    ll best = suf[0];
    int idx = -1;
    for (int i = 1; i < n; i++){
        if (a[i] > 0){
            ll score = pre[i - 1] + suf[i + 1] - a[i];
            if (score > best){
                best = score;
                idx = i;
            }
        }
    }

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

    vector<int> ans;
    for (int i = idx - 1; i >= 0; i--){
        if (ans.size() & 1)
            a[i] = -a[i];
        if (a[i] > 0)
            ans.push_back(i);
    }
    ans.push_back(idx);

    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Try solving the problem on a binary array; that is, all values of $$$a$$$ and $$$b$$$ are either $$$0$$$ or $$$1$$$.

Suppose you want to check if it is possible to achieve a final value of at least $$$m$$$. Then you can replace all smaller values with $$$0$$$, and all values at least $$$m$$$ with $$$1$$$. Now, solve the problem on the resulting binary array and check if it is possible to achieve a final value of $$$1$$$.

This allows you to binary search for the final answer.

Read the hints. It now suffices to solve the problem on a binary array. Let $$$\mathrm{diff} = \mathrm{cnt}_1 - \mathrm{cnt}_0$$$. Whenever you apply an operation, you lose the minimum and maximum of $$$S$$$. Therefore, the only way to change the value of $$$\mathrm{diff}$$$ is to apply an operation where the minimum and maximum of $$$S$$$ are the same; that is, all four values in $$$S$$$ are the same. If they are $$$0$$$, then $$$\mathrm{diff}$$$ increases by $$$2$$$; if they are $$$1$$$, then $$$\mathrm{diff}$$$ decreases by $$$2$$$. We want to increase $$$\mathrm{diff}$$$ as much as possible; if we can make it positive in the end, then that implies the final two values are both $$$1$$$.

Consider a subarray of indices such that there are no occurrences of $$${a_i, b_i} = {1, 1}$$$; that is, we only have either $$${a_i, b_i} = {0, 0}$$$ or $$${a_i, b_i} = {0, 1}$$$. Then we want to repeatedly perform operations within this subarray, because this will maximize the number of times we can increase $$$\mathrm{diff}$$$. Note that an operation using $$${0, 0}$$$ and $$${0, 1}$$$ will produce a $$${0, 0}$$$, so we will never lose an opportunity to increase $$$\mathrm{diff}$$$; we can apply operations within this subarray arbitrarily. Once we have applied as many operations as possible in this subarray, we are left with one pair, which is $$${0, 0}$$$ if the subarray started with a $$${0, 0}$$$, or $$${0, 1}$$$ otherwise.

Now, it is impossible to increase $$$\mathrm{diff}$$$ any further. This is because any two pairs of $$${0, 0}$$$ have a $$${1, 1}$$$ in between. Clearly, if $$$\mathrm{diff}$$$ is nonpositive, then we have already lost. If $$$\mathrm{diff}$$$ is positive, we claim we win. Indeed, if there exists any $$${0, 0}$$$ or $$${0, 1}$$$, we can perform any operation with it, thus avoiding decreasing $$$\mathrm{diff}$$$. Otherwise, if all pairs are equal to $$${1, 1}$$$, then we win trivially. This concludes the solution.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

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

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    int l = 0, r = 1e9 + 5;
    while (l < r){
        int mid = (l + r) / 2;

        int one = 0, zero = 0;
        int prev = -1;
        for (int i = 0; i < n; i++){
            int type = 0;
            if (a[i] >= mid)
                type++;
            if (b[i] >= mid)
                type++;

            if (type == 1)
                continue;

            if (type == 2){
                one++;
                prev = 1;
            }

            if (type == 0){
                if (prev != 0)
                    zero++;
                prev = 0;
            }
        }

        if (one > zero)
            l = mid + 1;
        else
            r = mid;
    }

    cout << l - 1 << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

$$$n$$$ will never be removed, and will always be added to $$$S$$$.

Try rooting at $$$n$$$.

Read the hints, through this editorial I will consider $$$n$$$ to be the root of the tree.

Lets try to determine the following for each node. When we add $$$x$$$ to $$$S$$$ for the first time, what can the largest element of $$$S$$$ be before this point. Lets try to find some necessary conditions for this.

• $$$\max(S) \lt x$$$, this is true because the maximum leaf is non-decreasing.
• $$$\max(S)$$$ is greater than the largest element in the subtree of $$$x$$$ (excluding $$$x$$$ itself). Since $$$n$$$ can never be removed, in order for $$$x$$$ to become a leaf, we must first remove everything in its subtree. For this to happen there must be some leaf outside the subtree of $$$x$$$ which is bigger than each element of the subtree. During this process a greater element will be added to $$$S$$$.

$$$\text{subtree}(x)$$$ will be used to denote the subtree of $$$x$$$ excluding $$$x$$$ itself. Remember that we rooted the tree at $$$n$$$.

It turns out that these conditions are also sufficient. i.e. if $$$\max(\text{subtree}(x)) \lt \max(S) \lt x$$$, then we are able to add $$$x$$$ into $$$S$$$ without needing to include any additional elements ($$$S := S \cup \lbrace x \rbrace$$$). We can prove that this is true because if the current largest leaf is larger than $$$\max(\text{subtree}(x))$$$, then we are able to remove the entire subtree of $$$x$$$ without changing the maximum. $$$x$$$ now becomes a leaf and because $$$\max(S) \lt x$$$, $$$x$$$ will be the new maximum and added on the next turn.

Thus we can solve this problem with dynamic programming where $$$dp_i$$$ is the number of ways to reach a state where $$$\max(S) = i$$$. The initial state has only the max leaf set to $$$1$$$.

$$$dp_i$$$ can transition to $$$dp_j$$$ if and only if $$$\max(\text{subtree}(j)) \lt i \lt j$$$. These transitions conveniently form ranges, so we can simulate all the transitions using prefix sums in $$$O(n)$$$.

It should be note that transitions to $$$n$$$ are a special case, a node $$$x$$$ can transition to $$$n$$$ if and only if we can delete all children of $$$n$$$ excluding the one with $$$x$$$ in its subtree. In other words all nodes outside the subtree that contains $$$x$$$ are smaller than it.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://mirror.codeforces.com/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

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

    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (g[n - 1].size() == 1){
        cout << "1\n";
        return;
    }

    vector<int> mx(n);
    auto dfs = [&](auto self, int c, int p) -> void{
        for (int x : g[c]){
            if (x == p)
                continue;

            self(self, x, c);
            mx[c] = max({mx[c], x, mx[x]});
        }
    };
    dfs(dfs, n - 1, -1);

    set<int, greater<int>> s;
    for (int i = 0; i < n - 1; i++)
        s.insert(i);

    vector<int> cur;
    auto dfs2 = [&](auto self, int c, int p) -> void{
        s.erase(c);
        cur.push_back(c);

        for (int x : g[c]){
            if (x == p)
                continue;

            self(self, x, c);
        }
    };
    
    vector<bool> ok(n); // can transition to n
    for (int x : g[n - 1]){
        dfs2(dfs2, x, n - 1);

        for (int u : cur){
            if (u > (*s.begin()))
                ok[u] = true;
        }

        for (int u : cur)
            s.insert(u);
        cur.clear();
    }
    ok[n - 1] = true;

    int idx = -1;
    for (int i = 0; i < n; i++){
        if (g[i].size() == 1)
            idx = i;
    }

    vector<mint> dp(n), pre(n);
    dp[idx] = 1;
    pre[idx] = 1;
    for (int i = idx + 1; i < n - 1; i++){
        int l = mx[i] + 1;

        if (l < i){
            dp[i] = pre[i - 1];
            if (l > 0)
                dp[i] -= pre[l - 1];
        }

        pre[i] = dp[i] + pre[i - 1];
    }

    mint ans = 0;
    for (int i = 0; i < n; i++){
        if (ok[i])
            ans += dp[i];
    }

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Which element of $$$a$$$ is it optimal to use last?

Suppose you know which element you're placing last. Now what does the problem reduce to?

Binary search is your friend.

We will prove that it's optimal to place the maximum value of $$$a$$$ last in the array. After we've done that, the problem now becomes maximising the minimum value of $$$b$$$ after rearranging the rest of the values in $$$a$$$.

To maximise the minimum value of $$$b$$$, we can binary search it. To check whether it's $$$\le v$$$, we can do a bitmask DP which finds the maximum number of disjoint subsets of $$$a$$$ whose sum is $$$\ge v$$$, and check whether we have at least $$$k$$$ of them. There exists a simple greedy algorithm, once we have these subsets, to construct an ordering which gets us the value of v: we assign each subset to a position in array $$$b$$$, and simulate the process; whenever an index is chosen to be added to, we choose the highest remaining number from the corresponding subset.

We can make the bitmask dp in the form dp[mask] = maximum {number of groups, leftover}. There are $$$O(n)$$$ transitions from each mask (adding each possible extra element to the mask), so it runs in $$$O(2^n \cdot n)$$$. Since the difference between min and max in $$$b$$$ is at most $$$max(a)$$$, we can find an upper and lower bound for the binary search which are A apart, so time complexity ends up being $$$O(n \cdot 2^n \cdot log(A))$$$.

We can use this greedy algorithm to prove that $$$max(a)$$$ can always be placed last (let's call it $$$x$$$). Suppose we have an optimal rearrangement with $$$x$$$ not being last, and let's consider the set of values which go in each position in array $$$b$$$. Consider the last item added to the maximum pile (let's call it $$$y$$$) and the pile where $$$x$$$ was added. If we remove $$$y$$$ from its pile, its pile is now $$$min(b)$$$. If we remove $$$x$$$ from its pile and add $$$y$$$ to it, there are two cases: 1. $$$y$$$'s original pile is still the min. Greedily construct this min and add $$$x$$$ last, and $$$pile = ans - y + x \ge ans$$$ so it's a maximal construction. 2. $$$x$$$'s original pile is now the min. Greedily construct this min and add $$$x$$$ last, and $$$pile \ge ans - y - x + y + x = ans$$$ so it's a maximal construction.

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

typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<ll> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;


void solve() {
    int n, k; cin >> n >> k;
    vecin(aa, n); sort(all(aa));
    n --;
    ll extra = aa.back(); aa.pop_back();

    ll L = 0, R = extra * (ll)n;
    while (L != R) {
        ll mid = (L + R + 1) / 2;
        vector<pair<int, ll>> dp(1 << n, {0, 0});
        for (int i = 1; i < (1 << n); i ++) {
            for (int j = 0; (1 << j) <= i; j ++) {
                if (!(i & (1 << j))) continue;
                int res = i ^ (1 << j);
                pair<int, ll> cur = dp[res];
                cur.second += aa[j];
                if (cur.second >= mid)
                    cur = {cur.first + 1, 0};
                dp[i] = max(dp[i], cur);
            }
        }
        if (dp[(1 << n) - 1].first >= k)
            L = mid;
        else
            R = mid - 1;
    }
    cout << L + extra << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;

    cin >> tt;

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

When is it optimal to stay at a house for more than $$$1$$$ day?

Suppose you are staying at a house for more than $$$1$$$ day. When should you arrive at that house?

Suppose you are staying at a house for more than $$$1$$$ day. Which houses could you previously have come from?

First, observe that any house you stay at for longer than $$$1$$$ day should be a prefix maximum on the path from house $$$x$$$, otherwise it's at least as good to stay on the previous house with greater $$$h_i$$$ on the path from house $$$x$$$.

Also, if you are going to stay at a house for longer than $$$1$$$ day, it is optimal to reach it as early as possible. Assume you stay at it for longer than 1 day but also don't reach it as early as possible: if the previous house you stayed at for longer than $$$1$$$ day had greater or equal hospitality you could have stayed there instead for an extra day and it would not be worse, and if it had lower hospitality you should have reached the new house earlier.

Finally, if you are going to switch directions in an optimal solution, you should go all the way past house $$$x$$$ before switching directions again. This is because if you switch directions at a house that is not a prefix maximum, it would have been better to just stay at the last prefix maximum for longer; and if you switch directions at a prefix maximum, but don't immediately go all the way past $$$x$$$, you should have stayed at that prefix maximum for longer.

We can maintain for each house the maximum possible satisfaction we can achieve if we reach it as early as possible. We know that for each house, the optimal answer if we finish on that house at time $$$y$$$ depends only on the house with the next largest $$$h_i$$$ on the path to $$$x$$$, and the maximum answer for having previously stayed on the other side of $$$x$$$ then gone straight to that house.

For the former case, we can maintain which house is the prefix maximum on both sides, and for the latter case, we can use convex hull trick or LCT to keep track of the best satisfaction if we arrive on house $$$x$$$ at exactly time $$$y$$$ from either side. We use two pointers for the leftmost and rightmost currently reachable houses and update whenever a new prefix maximum becomes reachable. We also need prefix sums to track the increase in satisfaction of any houses we pass on the path to the next prefix maximum. You also need to be careful to not immediately insert a new house into the CHT/LCT, but only as soon as the next prefix maximum on the other side can actually reach it. The implementation is a bit horrible and the time complexity is $$$O(n log n)$$$, although it can also be implemented in $$$O(n)$$$.

Suppose you are staying at a house for more than $$$1$$$ day. Which houses could you go to next?

The boring solution uses a "pull DP". What if instead we used a "push DP"? In fact, we can show that whenever you reach a prefix maximum, the next house you will move to is either the next higher prefix maximum on that side of $$$x$$$, or the next highest prefix maximum on the other side of $$$x$$$. So we can precalculate both those things using a monotonic stack, and perform the transitions to both those houses (if they exist), assuming we reach them as early as possible. This is easy to implement in $$$O(n)$$$.

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

typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<ll> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;


struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
    ll eval(ll x) { return k * x + m; }
};

struct LineContainer : multiset<Line, less<>> {
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) {
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.eval(x);
	}
};

vector<ll> h;
vector<ll> pref;

ll range_sum(int L, int R) {
    return pref[R + 1] - pref[L];
}

void solve() {
    int n, t, x; cin >> n >> t >> x;
    x --;
    h.resize(n); pref.resize(n + 1);
    pref[0] = 0;
    for (int i = 0; i < n; i ++) {
        cin >> h[i];
        pref[i + 1] = pref[i] + h[i];
    }
    vecin(d, n - 1);
    for (int i = x - 2; i >= 0; i --) {
        d[i] = max(d[i], d[i + 1] + 1);
    }
    for (int i = x; i < n - 2; i ++) {
        d[i + 1] = max(d[i + 1], d[i] + 1);
    }

    ll ans = h[x] * t;
    int L = x, R = x;
    Line curleft = {h[x], 0, 0}, curright = {h[x], 0, 0};
    int left_best = x, right_best = x;
    LineContainer left, right;
    left.add(h[x], 0); right.add(h[x], 0);
    queue<pair<int, pair<ll, ll>>> add_left, add_right;
    while (L > 0 || R < n - 1) {
        int left_time = (L == 0) ? 2e9 : d[L - 1];
        int right_time = (R == n - 1) ? 2e9 : d[R];
        if (min(left_time, right_time) > t) break;
        if (left_time <= right_time) {
            L --;
            if (h[L] > curleft.k) {
                // best = max sum on day left_time-1 on house L+1
                int pref_dist = left_best - L;
                int start_dist = x - L;
                while (add_right.size() && add_right.front().first <= left_time - start_dist) {
                    right.add(add_right.front().second.first, add_right.front().second.second);
                    add_right.pop();
                }
                ll best = max(
                    curleft.eval(left_time - pref_dist) + range_sum(L + 1, left_best - 1),
                    right.query(left_time - start_dist) + range_sum(L + 1, x - 1)
                );
                // cout << L << " " << h[L] << " " << best << endl;
                ans = max(ans, best + (t - left_time + 1) * h[L]);
                left_best = L;
                curleft = {h[L], best - (left_time - 1) * h[L], 0};
                add_left.push({left_time + start_dist, {h[L], best - (left_time - 1 + start_dist) * h[L] + range_sum(L + 1, x)}});
            }
        } else {
            R ++;
            if (h[R] > curright.k) {
                // best = max sum on day right_time-1 on house R-1
                int pref_dist = R - right_best;
                int start_dist = R - x;
                while (add_left.size() && add_left.front().first <= right_time - start_dist) {
                    left.add(add_left.front().second.first, add_left.front().second.second);
                    add_left.pop();
                }
                ll best = max(
                    curright.eval(right_time - pref_dist) + range_sum(right_best + 1, R - 1),
                    left.query(right_time - start_dist) + range_sum(x + 1, R - 1)
                );
                // cout << R << " " << h[R] << " " << best << endl;
                ans = max(ans, best + (t - right_time + 1) * h[R]);
                right_best = R;
                curright = {h[R], best - (right_time - 1) * h[R], 0};
                add_right.push({right_time + start_dist, {h[R], best - (right_time - 1 + start_dist) * h[R] + range_sum(x, R - 1)}});
            }
        }
    }
    cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;

    cin >> tt;

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

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
template <class T>
using vc = vector<T>;
 
template <class T>
constexpr T infty = 0;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
 
#define FOR2(i, a) for (int i = 0; i < int(a); ++i)
#define FOR3(i, a, b) for (int i = int(a); i < int(b); ++i)
#define FOR2_R(i, a) for (int i = int(a) - 1; i >= 0; --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, _4, FOR3, FOR2, _1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, _3, FOR2_R, _1)(__VA_ARGS__)
 
#define all(x) (x).begin(), (x).end()
#define trav(a, x) for (auto& a : x)
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
 
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    T c = max<T>(a, b);
    bool changed = (c != a);
    a = c;
    return changed;
}
 
template <class T>
void rd(T &x) { cin >> x; }
 
template <class T>
void rd(vc<T> &x) { for (auto &d : x) rd(d); }
 
void read() {}
template <class H, class... T>
void read(H &h, T &...t) { rd(h), read(t...); }
 
void print() { cout << '\n'; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}
 
#define INT(...)   int __VA_ARGS__; read(__VA_ARGS__)
#define LL(...)    ll __VA_ARGS__; read(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); read(name)
 




void solve() {
    INT(N); LL(tot); INT(X);
    X--;
    VEC(ll, A, N);
    VEC(ll, D, N-1);
    vl T(N);
    T[X] = 1;
    FOR(i, X, N-1) {
        T[i+1] = max(T[i]+1, D[i]);
        if (i == X && D[i] == 1) T[i+1] = 1;
    }
    FOR_R(i, X) {
        T[i] = max(T[i+1]+1, D[i]);
        if (i == X-1 && D[i] == 1) T[i] = 1;
    }
    vi nh(N), lh(N);
    vc<pl> stk;
    stk.eb(mp(N, 2e9));
    FOR_R(i, N) {
        while (stk.back().se <= A[i]) stk.pop_back();
        nh[i] = stk.back().fi;
        stk.eb(mp(i, A[i]));
    }
    stk.clear();
    stk.eb(mp(-1, 2e9));
    FOR(i, N) {
        while (stk.back().se <= A[i]) stk.pop_back();
        lh[i] = stk.back().fi;
        stk.eb(mp(i, A[i]));
    }
 
    ll dp[N];
    FOR(i, N) {
        dp[i] = -infty<ll>;
    }
    FOR(i, N) dp[i] = 0;
    vc<pl> vals; FOR(i, N) vals.eb(mp(T[i], i));
    sort(all(vals));
    ll ans = 0;
    vl ps; ps.eb(0);
    FOR(i, N) ps.eb(ps.back()+A[i]);
    trav(xx, vals) {
        int i = xx.se;
        if (dp[i] < 0) continue;
        chmax(ans, (tot - T[i] + 1) * A[i] + dp[i]);
        vi ops = {nh[i], lh[i]};
        trav(j, ops) {
            if (j < 0 || j >= N) continue;
            if (abs(j-i) > T[j] - T[i]) {
                continue;
            }
            chmax(dp[j], dp[i] + (T[j] - T[i] - abs(j-i) + 1) * A[i] + ps[max(i, j)] - ps[min(i, j) + 1]);
        }
    }
 
    print(ans);
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    INT(T);
    FOR(t, T) {
        solve();
    }
    return 0;
}

Imagine the string has no $$$\mathtt{?}$$$ characters, try to find a greedy which can check if a string $$$t$$$ can be generated from $$$s$$$ by applying the operation.

Try to generalise this greedy for when there are $$$\mathtt{?}$$$ characters.

Read the hints. A correct greedy for the no $$$\mathtt{?}$$$ character version is perhaps the simplest one you can try, which is as follows:

We would like to find a subsequence of $$$s$$$ which is equal to $$$t$$$, where each substring between consecutive characters contains an even number of $$$\mathtt{1}$$$. We can find this by iterating through the characters of $$$t$$$. For each character find the first character in $$$s$$$ where $$$s_j = t_i$$$ and the substring between $$$s_j$$$ and the previously chosen character contains an even number of $$$\mathtt{1}$$$.

We can prove correctness by contradiction. Say we have a matching where at some point we didn't chose the earliest match, say between $$$t_i$$$ and $$$t_{i + 1}$$$ (we matched with a later position for $$$t_{i + 1}$$$). We can adjust our matching to instead take the earliest position for $$$t_{i + 1}$$$, call this earliest position $$$x$$$. Since we know the substring from $$$t_i$$$ to $$$x$$$ is removable and the substring from $$$t_i$$$ to $$$t_{i + 1}$$$ is removable, we can deduce that the substring from $$$x$$$ to $$$t_{i + 1}$$$ is removable. Because $$$t_{i + 1}$$$ to $$$t_{i + 2}$$$ is removeable and $$$x$$$ to $$$t_{i + 1}$$$ is removable, we can deduce that $$$x$$$ to $$$t_{i + 2}$$$ will also be removable. Thus matching the earliest option is always optimal.

Now lets try to generalise this when there are $$$\mathtt{?}$$$ characters. Naïvely using the same greedy does not work, consider a case like $$$s = \mathtt{?10000000}$$$, $$$t = \mathtt{10000000}$$$. If we match the first $$$\mathtt{1}$$$ with the $$$\mathtt{?}$$$ we get stuck, instead we should set the $$$\mathtt{?}$$$ to $$$\mathtt{0}$$$ and match with the $$$\mathtt{1}$$$.

Let's analyse why we fail this counter case. It fails because we incorrectly assign the value of a $$$\mathtt{?}$$$, and in general this will always be why the greedy fails, since we already know this approach would be correct after replacing all $$$\mathtt{?}$$$. When we encounter a $$$\mathtt{?}$$$ during the greedy, our choice of replacement determines the parity of the count of $$$\mathtt{1}$$$ in the current suffix. If chose incorrectly we get "locked" on the incorrect parity and are forced to consume suboptimally.

To fix this problem, we can adjust our greedy to consider both parities at the same time. Instead of considering only the earliest match, we consider the earliest match for each parity. For each character $$$t_i$$$, we will compute the pair $$$(\text{best}_0, \text{best}_1)$$$, where $$$\text{best}_0$$$ is the earliest match with an even count of $$$1$$$ in the suffix and $$$\text{best}_1$$$ is the earliest match with an odd count of $$$1$$$ in the suffix (note that each $$$\mathtt{?}$$$ does not contribute to the suffix parity). When we transition we only need to consider the $$$4$$$ combinations of new parity and old parity. Now the entire string will be generatable if and only if the substring $$$s_{best_i + 1},s_{best_i + 2},\ldots,s_n$$$ is removable for at least one element of the final pair.

The proof for this greedy is similar to the naïve greedy in the no $$$\mathtt{?}$$$ version. However this time we prove that for any step, if we fix the parity of the new suffix, then taking the earliest choice is always optimal. And now since we always consider both suffix parities, we will always find a matching if one exists.

Now for counting, we can run dynamic programming on this greedy. Where $$$dp_{i, j}$$$ is the number of strings with ending greedy pair $$$(i, j)$$$, for transitions we only need to try appending $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ to the string. To fit the time limit of the problem, we need to be able to find transitions in $$$O(1)$$$. Because the problem allows $$$O(n^2)$$$ anyway, we can pre-calculate the earliest even and odd match for each position. This allows us to calculate the transitions for pairs in $$$O(1)$$$.

Thus, the final time complexity is $$$O(n^2)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://mirror.codeforces.com/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

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

    string s;
    cin >> s;

    s = '0' + s;
    n++;

    vector<int> pre(n);
    pre[0] = s[0] == '1';
    for (int i = 1; i < n; i++){
        pre[i] = pre[i - 1] + (s[i] == '1');
    }

    vector<array<array<int, 2>, 2>> to(n + 1);
    for (int i = 0; i <= n; i++){
        to[i][0][0] = n;
        to[i][0][1] = n;
        to[i][1][0] = n;
        to[i][1][1] = n;

        int cnt = 0;
        bool wowee = false;
        for (int j = i + 1; j < n; j++){
            if ((cnt & 1) && !wowee){
                if (s[j] == '1')
                    cnt++;
                if (s[j] == '?')
                    wowee = true;
                continue;
            }
            
            if (s[j] == '1')
                cnt++;
            if (s[j] == '?')
                wowee = true;

            int par = pre[j] & 1;
            if (s[j] == '?'){
                to[i][0][par] = min(to[i][0][par], j);
                to[i][1][par] = min(to[i][1][par], j);
                continue;
            }

            int omg = s[j] - '0';
            to[i][omg][par] = min(to[i][omg][par], j);
        }
    }

    vector<bool> good(n + 1);
    int cnt = 0;
    int wowee = false;
    for (int i = n - 1; i >= 0; i--){
        good[i] = (cnt % 2 == 0) || wowee;
        if (s[i] == '1')
            cnt++;
        if (s[i] == '?')
            wowee = true;
    }

    mint ans = 0;
    vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
    dp[0][n] = 1;

    vector<array<int, 2>> ord;
    for (int i = 0; i <= n; i++){
        for (int j = i; j <= n; j++){
            ord.push_back({i, j});
            if (j != i)
                ord.push_back({j, i});
        }
    }

    for (auto [i, j] : ord){
        for (int nxt = 0; nxt < 2; nxt++){
            int even = min(to[i][nxt][0], to[j][nxt][0]);
            int odd = min(to[i][nxt][1], to[j][nxt][1]);
            dp[even][odd] += dp[i][j];
        }

        if (good[i] || good[j])
            ans += dp[i][j];
    }

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

It's not convex, monotone, monge, FFT, centroid, or any other fancy trick like that. The solution is simpler than you might expect.

Reformulate the formula for score so that it's in terms of nodes in the subtree from root, not the path to the root.

Suppose you wanted to solve for a single root in $$$O(n^2)$$$. How would you do it?

Why is naive rerooting $$$O(n^3)$$$ on a tree like this?

How many DP values do you compute for the node labelled X? How many do you actually care about?

In general, how many DP values do you actually care about for a node?

Let:

• $$$dp_1[i][j]$$$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $$$i$$$, assuming the selected root is $$$i$$$ or an ancestor of $$$i$$$, which uses exactly $$$j$$$ nodes.
• $$$dp_2[i][j]$$$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $$$i$$$ assuming the selected root is $$$i$$$ or an ancestor of $$$i$$$, which uses exactly $$$j$$$ nodes, and does not have node $$$i$$$ selected.
• $$$dp_3[i][j]$$$ be the maximum score of a subset of nodes \textbf{outside} the subtree of node $$$i$$$, assuming the selected root is $$$i$$$ or in its subtree, which uses exactly $$$j$$$ nodes.

We can compute $$$dp_1$$$ and $$$dp_2$$$ using Trick 7 in $$$O(n^2)$$$. The tricky part is $$$dp_3$$$. The critical observation is that for each node $$$i$$$ with a subtree size of $$$sz(i)$$$, we only care about the $$$sz(i)$$$ largest values of $$$dp_3[i]$$$, that is: $$$dp_3[i][k - sz(i)], dp_3[i][k - sz(i) + 1], \ldots, dp3_[i][k - 1]$$$. This is because if we select fewer than $$$k - sz(i)$$$ nodes outside of the subtree of $$$i$$$, then we have selected fewer than $$$k$$$ nodes overall and the solution is not optimal. There are now two ways to continue.

Let us compute $$$dp_3$$$ in a way similar to Trick 7. Initially we have $$$dp_3[0][j] = 0$$$ for all $$$j$$$ (since the root has no parents).

Suppose we are at a node $$$u$$$ with children $$$c_1, c_2, \ldots, c_m$$$ and we have already computed $$$dp_3[u]$$$. Let $$$pref[i][j]$$$ be the max score we can achieve by selecting $$$j$$$ nodes out of the subtrees of $$$c_1, \ldots, c_i$$$. And let $$$suf[i][j]$$$ be the max score we can achieve by selecting $$$j$$$ nodes out of the subtrees of $$$c_i, \ldots, c_m$$$ and nodes outside of the subtree of $$$u$$$. Then for each child we obtain the largest $$$sz(c_i0$$$ values of $$$dp_3[c_i]$$$ by merging $$$pref[i - 1]$$$ and $$$suf[i + 1]$$$.

Observe that we only need to compute $$$\Sigma_{j\le i}sz(c_i)$$$ values of $$$pref[i]$$$, and $$$\Sigma_{j\ge i}sz(c_i)$$$ values of $$$suf[i]$$$. So by the same argument as Trick 7 running in $$$O(n^2)$$$, this DP also runs in $$$O(n^2)$$$.

All that remains is to add the contribution of node $$$u$$$ to each of its child values with $$$dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$$$. Then the answer for each root is $$$max(dp_2[x][j] + dp_3[x][k - 1 - j] + k \cdot w[i])$$$.

Suppose the tree is a binary tree. Then, for a node $$$u$$$ with children $$$c_1, c_2$$$, we can just naively merge $$$dp_1[c_2]$$$ and $$$dp_3[u]$$$ to get $$$dp_3[c_1]$$$, and merge $$$dp_1[c_1]$$$ and $$$dp_3[u]$$$ to get $$$dp_3[c_2]$$$ (then add the contribution of $$$u$$$ with $$$dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$$$). And this magically runs in $$$O(n^2)$$$, because both the convolutions run in $$$sz(c_1) \cdot sz(c_2)$$$, and the sum across all nodes of $$$sz(c_1) \cdot sz(c_2)$$$ exactly corresponds to each pair of nodes once.

What if the tree is not a binary tree? We can make it one! If a node $$$u$$$ has $$$m$$$ children, add $$$m-3$$$ dummy nodes $$$d_1, d_2, \ldots, d_{m-3}$$$ in a chain and connect the children to them like this:

The only thing to watch out for is that the contribution of the original node $$$u$$$ must be done for each original child, not for the dummy nodes. The number of nodes is still $$$O(n)$$$ so it runs in $$$O(n^2)$$$.

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

typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;

const int MAXN = 4005;

ll dp_down[MAXN][MAXN], dp_down_take[MAXN][MAXN], dp_up[MAXN][MAXN];
ll pref_merge[MAXN][MAXN], suff_merge[MAXN][MAXN];
vector<int> adj[MAXN];
vector<int> children[MAXN];
ll weight[MAXN];
int sz[MAXN];
int n, k;

void dfs1(int node, int parent) {
    sz[node] = 1;
    for (auto a : adj[node])
        if (a != parent) {
            children[node].push_back(a);
            dfs1(a, node);
            for (int i = min(sz[node] - 1, k); i >= 0; i --)
                for (int j = 1; j <= sz[a] && i + j <= k; j ++)
                    dp_down[node][i + j] = max(dp_down[node][i + j], dp_down[node][i] + dp_down_take[a][j]);
            sz[node] += sz[a];
        }
    for (int i = min(k, sz[node]); i > 0; i --)
        dp_down_take[node][i] = max(dp_down[node][i], dp_down[node][i - 1] + (ll)i * weight[node]);
}

void dfs2(int node) {
    int deg = children[node].size();
    if (deg == 1) {
        for (int i = 0; i <= k; i ++)
            dp_up[children[node][0]][i] = dp_up[node][i];
    } else if (deg >= 2) {
        int p = sz[children[node][0]];
        for (int i = 0; i <= k; i ++)
            pref_merge[0][i] = dp_down_take[children[node][0]][i],
            suff_merge[deg][i] = dp_up[node][i];
        for (int c = 1; c < deg; c ++) {
            for (int i = 0; i <= k; i ++)
                pref_merge[c][i] = 0;
            int child = children[node][c];
            p += sz[child];
            for (int i = min(k, p); i >= 0; i --)
                for (int j = min(i, sz[child]); j >= 0 && i - j <= p - sz[child]; j --)
                    pref_merge[c][i] = max(pref_merge[c][i], pref_merge[c - 1][i - j] + dp_down_take[child][j]);
        }
        for (int c = deg - 1; c >= 0; c --) {
            for (int i = 0; i <= k; i ++)
                suff_merge[c][i] = 0;
            int child = children[node][c];
            p -= sz[child];
            for (int i = k; i >= max(0, k - p - 1); i --)
                for (int j = min(i, sz[child]); j >= 0; j --)
                    suff_merge[c][i] = max(suff_merge[c][i], suff_merge[c + 1][i - j] + dp_down_take[child][j]);
            for (int i = k; i >= max(0, k - sz[child] - 1); i --)
                for (int j = min(i, p); j >= 0; j --)
                    dp_up[child][i] = max(dp_up[child][i], suff_merge[c + 1][i - j] + (c > 0 ? pref_merge[c - 1][j] : 0));
        }
    }
    for (auto a : children[node]) {
        for (int i = min(k, n - sz[a]); i >= 1; i --)
            dp_up[a][i] = max(dp_up[a][i], dp_up[a][i - 1] + (ll)i * weight[node]);
        dfs2(a);
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j <= k; j ++)
            dp_down[i][j] = dp_down_take[i][j] = dp_up[i][j] = 0;
        adj[i].clear(); children[i].clear();
        cin >> weight[i];
    }
    for (int i = 0; i < n - 1; i ++) {
        int a, b; cin >> a >> b;
        a --; b --;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs1(0, -1);
    dfs2(0);
    for (int i = 0; i < n; i ++) {
        ll best = 0;
        for (int j = 0; j < min(k, sz[i]); j ++)
            best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * weight[i]);
        cout << best << " ";
    }
    cout << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;

    cin >> tt;

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

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;
 
const int MAXN = 4005;
int n, k;
int spare;
vector<int> adj[MAXN], children[2 * MAXN];
ll beauty[2 * MAXN];
int sz[2 * MAXN];
ll dp_down[2 * MAXN][MAXN], dp_down_take[2 * MAXN][MAXN];
ll dp_up[2 * MAXN][MAXN];
 
void merge(ll *target, ll *aa, ll *bb, int tsize, int asize, int bsize, int topmost) {
    for (int i = tsize; i > max(0, tsize - topmost); i --)
        for (int j = 0; j <= min(min(asize, bsize), i); j ++)
            target[i] = max(target[i], asize >= bsize ? aa[i - j] + bb[j] : bb[i - j] + aa[j]);
}
void finalise(ll *target, ll *source, ll b, int tsize) {
    for (int i = tsize; i > 0; i --)
        target[i] = max(source[i], source[i - 1] + (ll)i * b);
}
 
void dfs1(int node, int parent) {
    vector<int> cc;
    for (auto a : adj[node])
        if (a != parent) {
            dfs1(a, node);
            cc.push_back(a);
        }
    int cur = node;
    while (cc.size() > 2) {
        children[cur] = {cc.back(), spare};
        cc.pop_back();
        beauty[spare] = beauty[node];
        cur = spare ++;
    }
    children[cur] = cc;
}
 
void dfs2(int node) {
    sz[node] = (node < n);
    for (auto a : children[node]) {
        dfs2(a);
        sz[node] += sz[a];
    }
    if (children[node].size() == 1) {
        for (int i = 0; i <= k; i ++)
            dp_down[node][i] = dp_down_take[children[node][0]][i];
    } else if (children[node].size() == 2) {
        merge(dp_down[node], dp_down_take[children[node][0]], dp_down_take[children[node][1]], min(k, sz[node] - (node < n)), sz[children[node][0]], sz[children[node][1]], sz[node] - (node < n));
    }
    finalise(dp_down_take[node], dp_down[node], node < n ? beauty[node] : 0, min(k, sz[node]));
}
 
void dfs3(int node) {
    if (children[node].size() == 1) {
        finalise(dp_up[children[node][0]], dp_up[node], beauty[node], min(k, n - sz[children[node][0]]));
    } else if (children[node].size() == 2) {
        int aa = children[node][0], bb = children[node][1];
        merge(dp_up[aa], dp_up[node], dp_down_take[bb], min(n - sz[aa], k), min(n - sz[node], k), min(sz[bb], k), min(sz[aa] + 2, k));
        merge(dp_up[bb], dp_up[node], dp_down_take[aa], min(n - sz[bb], k), min(n - sz[node], k), min(sz[aa], k), min(sz[bb] + 2, k));
        if (aa < n)
            finalise(dp_up[aa], dp_up[aa], beauty[node], min(n - sz[aa], k));
        if (bb < n)
            finalise(dp_up[bb], dp_up[bb], beauty[node], min(n - sz[bb], k));
    }
    for (auto a : children[node])
        dfs3(a);
}
 
void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++)
        adj[i].clear(), children[i].clear();
    for (int i = n; i < 2 * n; i ++)
        children[i].clear();
    spare = n;
    for (int i = 0; i < n; i ++)
        cin >> beauty[i];
    for (int i = 0; i < n - 1; i ++) {
        int a, b; cin >> a >> b;
        a --; b --;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs1(0, -1);
    for (int i = 0; i < spare; i ++)
        for (int j = 0; j <= k; j ++)
            dp_down[i][j] = dp_up[i][j] = dp_down_take[i][j] = 0;
    dfs2(0);
    dfs3(0);
    for (int i = 0; i < n; i ++) {
        ll best = 0;
        for (int j = 0; j < min(k, sz[i]); j ++)
            best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * beauty[i]);
        cout << best << " ";
    }
    cout << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;
 
    cin >> tt;
 
    while (tt--) solve();
    return 0;
}

My solution was the same as blackscreen1's solution, but I found it in a different way. First, I tried binary searching on the answer, so it reduces to checking if $$$P[i] - i \leq K$$$.

Rather than setting $$$P^{-1}[0], P^{-1}[1], \cdots$$$, giving each index $$$i$$$ a deadline of $$$i + K$$$, I decided to use the reverse order; first set $$$P^{-1}[N-1]$$$, then $$$P^{-1}[N-2]$$$, and so on. This means that each index $$$i$$$ is only "usable" from "time" $$$i+K$$$ onwards. Then, $$$P^{-1}[i]$$$ must be the remaining student with highest $$$A$$$ or highest $$$B$$$.

Now, the key observation is that the only way we can "die" is if none of these two students are usable. This means that there is no "better" student to choose; Both choices simply remove a student from the current pool of "viable" students (a viable student is a student that can be removed at the current point in time by repeatedly removing a usable student with highest $$$A$$$ or highest $$$B$$$).

Going back to the main bugaboo, it becomes obvious that we should choose the remaining student with higher index as $$$P^{-1}[i]$$$; if $$$\text{ans} \lt i - (\text{lower index})$$$, we have to choose the higher one to proceed; if $$$\text{ans} \geq i - (\text{lower index})$$$, choosing either student is fine. In both cases, choosing the higher index is not harmful.

#include "exam.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v),end(v)
#define REP(i,a,b) for(int i=a;i<b;i++)

int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B) {
	vector<int> apq(N), bpq(N);
	for(int i=0;i<N;i++) {
		apq[A[i]] = i;
		bpq[B[i]] = i;
	}
	bool taken[N];
	memset(taken,0,sizeof(taken));
	int ans = 0;
	for(int i=N;i--;) {
		while(taken[apq.back()])
			apq.pop_back();
		while(taken[bpq.back()])
			bpq.pop_back();
		if(apq.back() > bpq.back()) {
			taken[apq.back()] = 1;
			ans = max(ans, i - apq.back());
		} else {
			taken[bpq.back()] = 1;
			ans = max(ans, i - bpq.back());
		}
	}
	return ans;
}

I first created a provisional country list as follows: When we see a student with rank $$$x$$$, find a country with exactly $$$x$$$ people, and add the student to the country.

Note that whenever two countries have the same number of people, we can swap them and get another valid assignment. This means that if country $$$1$$$ and country $$$2$$$ both have $$$k$$$ people at some point in time, the $$$\geq (k+1)^{st}$$$ and $$$\leq k^{th}$$$ people in country $$$1$$$ do not necessarily belong to the same country.

Thus, for each country, we can store all these "cut points", and use them to find the consecutive ranges of people guaranteed to be in the same country.

#include "country.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v),end(v)
#define REP(i,a,b) for(int i=a;i<b;i++)

long long count_same_country(int N, std::vector<int> country_rank) {
	vector<int> ppl(N,0);
	vector<int> time[N];
	for(int x: country_rank) {
		int add = upper_bound(all(ppl),x) - begin(ppl) - 1;
		ppl[add]++;
		if(add != N - 1 && ppl[add] == ppl[add+1]) {
			time[add].push_back(ppl[add]);
			time[add+1].push_back(ppl[add]);
		}
	}
	long long ans = 0;
	for(int i=0;i<N;i++) {
		int prv = 0;
		for(int x: time[i]) {
			ans += (x - prv) * (x - prv - 1LL) / 2;
			prv = x;
		}
		ans += (ppl[i] - prv) * (ppl[i] - prv - 1LL) / 2;
	}
	return ans;
}

My solution was the same as blackscreen1's solution, but I found it in a different way.

Define a country state as a pair containing the current "time" (i.e. the number of students already processed) and the number of people in the country. We can draw a graph of country states, where an edge from $$$(t, cnt)$$$ to $$$(t+1, cnt_1)$$$ means there is a country with $$$cnt$$$ people at time $$$t$$$, and $$$cnt_1$$$ people at time $$$t+1$$$.

Claim: Suppose that:

• there exists a path from $$$(0,0)$$$ to $$$(t_1, x_1)$$$
• $$$t_0 \leq t_1$$$
• There exists a path from $$$(t_0, x_0)$$$ to $$$(t_1, l)$$$ and $$$l \leq x_1$$$
• There exists a path from $$$(t_0, x_0)$$$ to $$$(t_1, r)$$$ and $$$r \geq x_1$$$

Then there exists a path from $$$(t_0, x_0)$$$ to $$$(t_1, x_1)$$$.

Proof:

Thus, for each student, we just need to keep track of the leftmost and rightmost points it can end up in at various points in time. Since we only care about the number of students, we can use two frequency arrays, $$$L$$$ and $$$R$$$. Refer to the implementation for more details.

struct fenwick {
	int n;
	vector<int> f;
	fenwick(int _n): n(_n+1), f(_n+1,0) {}
	void up(int x, int u) {
		for(x++;x<n;x+=(x&-x))
			f[x] += u;
	}
	int qry(int x) {
		int ans = 0;
		for(x++;x;x-=(x&-x))
			ans += f[x];
		return ans;
	}
};
long long count_diff_country(int N, std::vector<int> country_rank) {
	fenwick lft(N), rgt(N);
	long long ans = 0;
	vector<int> ppl(N,0);
	for(int i=0;i<N;i++) {
		int x = country_rank[i];
		int add = upper_bound(all(ppl),x) - begin(ppl) - 1;
		int lx = lft.qry(x);
		int lxm = lft.qry(x-1);
		int rx = rgt.qry(x);
		int rxm = rgt.qry(x-1);
		ans += i - lx;
		ans += rxm;
		rgt.up(x+1,rx - rxm);
		rgt.up(x,-(rx - rxm));
		if(add == 0 || ppl[add-1] < x) {
			lft.up(x+1,lx - lxm);
			lft.up(x,-(lx - lxm));
		}
		ppl[add]++;
		rgt.up(x+1,1);
		lft.up(x+1,1);
	}
	return ans;
}

Ideas

Looking at the $$$W \leq 1$$$ subbugaboo, we see that it is helpful to colour nodes based on the XOR of edges on the path to $$$0$$$. Let this value be $$$d_u$$$. In the $$$W \leq 1$$$ subbugaboo, the answer is $$$0$$$ if and only if there exists a common ancestor $$$L$$$ of $$$U$$$ and $$$V$$$, with $$$d_L = d_U = d_V$$$.

We can generalise this to compute $$$\lfloor \log_2 \text{ans} \rfloor$$$. We note that if $$$\text{ans} \lt 2^k$$$, we can only jump between nodes $$$u$$$ and $$$v$$$ with $$$d_u \oplus d_v \lt 2^k \implies (d_u \gg k) = (d_v \gg k)$$$. Thus, there must be a common ancestor $$$L$$$ of $$$U$$$ and $$$V$$$, with $$$(d_L \gg k) = (d_U \gg k) = (d_V \gg k)$$$. Let us compute $$$par(u,k)$$$ (which we will discuss later), the highest ancestor of $$$u$$$ such that $$$d_{par(u,k)} \gg k = d_u \gg k$$$. Then, this reduces to checking if $$$par(U,k)=par(V,k)$$$.

Suppose we have found out that $$$2^k \leq \text{ans} \lt 2^{k+1}$$$. Any jumps with $$$d_u \oplus d_v \lt 2^k$$$ are now "free". Using only "free jumps", we can jump from $$$U$$$ to any node $$$u$$$ such that $$$(d_u \gg k) = (d_U \gg k)$$$ and $$$u$$$ is a descendant of $$$par(U,k)$$$ (it is easy to check these two conditions are both necessary and sufficient). Call the set of such nodes $$$S_U$$$, and define $$$S_V$$$ similarly. Also, if $$$(d_u \gg (k+1)) \neq (d_v \gg (k+1))$$$, jumping from $$$u$$$ to $$$v$$$ is bad since $$$d_u \oplus d_v \geq 2^{k+1}$$$.

There are two cases here.

Case 1: $$$par(U,k)$$$ is an ancestor of $$$par(V,k)$$$.

In this case, $$$(d_V \gg k) \neq (d_U \gg k)$$$ (since if they were equal, $$$par(V,k)$$$ would not be the highest parent). In this case, to get from $$$U$$$ to $$$V$$$, we must jump from $$$S_U$$$ to $$$S_V$$$ at some point in time. Suppose we jump from $$$u \in S_U$$$ to $$$v \in S_V$$$. Then we need to minimise $$$d_u \oplus d_v$$$ over all such $$$u$$$ and $$$v$$$.

Let $$$x$$$ be the lower node. Then, we want to minimise $$$d_x \oplus d_y$$$, given that $$$y$$$ is an ancestor of $$$x$$$, and the most significant bit $$$d_x$$$ and $$$d_y$$$ differ is the $$$k$$$-th bit. Let this be $$$f(x,k)$$$. We thus have to find the minimum value of $$$f(x,k)$$$, where $$$x$$$ is in the subtree of $$$par(V,k)$$$ and $$$(d_x \gg (k+1)) = (d_{par(V,k)} \gg (k+1))$$$. Call this $$$g(par(V,k),k+1)$$$. We will discuss how to compute $$$f$$$ and $$$g$$$ later.

Case 2: $$$par(U,k)$$$ and $$$par(V,k)$$$ are not ancestors of each other.

In this case, we first jump out of the subtree of $$$par(U,k)$$$, for a cost of $$$g(par(U,k),k+1)$$$, then jump into the subtree of $$$par(V,k)$$$, for a cost of $$$g(par(V,k),k+1)$$$.

Implementation Notes

$$$par$$$ and $$$f$$$ can be computed easily with a trie. DFS from node $$$0$$$, and add $$$d_x$$$ to the trie when we enter it, then remove $$$d_x$$$ when we leave it.

I avoided implementation messiness by using an array segtree rather than pointers. I had an array of size $$$2^{21}$$$, and the left and right children of node $$$x$$$ are $$$2x$$$ and $$$2x+1$$$. The root is node $$$1$$$, and nodes $$$[2^{20},2^{21})$$$ are the leaves.

Note that $$$g(x,k)$$$ is the minimum value of $$$f(y,k-1)$$$ where $$$(d_y \gg k) = (d_x \gg k)$$$. We store a map, where the key is $$$(k, d_y \gg k)$$$, and the value is the minimum $$$f(y,k-1)$$$. Two maps can be merged using small-to-large merging to achieve a complexity of $$$N \log N \log A + Q \log \log A$$$. (Since I used regular rather than unordered maps, and found $$$k$$$ by linear search rather than binary search, my code's complexity was $$$N \log^2 N \log A + Q \log A$$$).

In my implementation, I lumped $$$(k, d_y \gg k)$$$ into a single integer.

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

int par[50'005][21];
map<int,int> mpScore[50'005];
int minScore[50'005][21];
int dist[50'005];
int pre[50'005], post[50'005];
int seg[1<<21];
void init(int N, std::vector<int> P, std::vector<int> W)  {
	fill(seg,seg+(1<<21),50005);
	vector<vector<pair<int,int>>> child(N);
	for(int i=1;i<N;i++)
		child[P[i]].push_back({i,W[i]});
	int cnt = 0;
	auto dfs = [&child,&cnt](auto &dfs, int x, int p) -> void {
		pre[x] = cnt++;
		int v = dist[x] + (1<<20);
		for(int i=v;i;i>>=1)
			seg[i] = min(seg[i],x);
		for(int i=0;i<21;i++)
			par[x][i] = seg[v>>i];
		for(int i=0;i<20;i++) {
			int cur = (v >> i) ^ 1;
			int j = i;
			if(seg[cur] == 50005)
				continue;
			while(cur < (1<<20)) {
				j--;
				int pref = (cur << 1) | ((v>>j) & 1);
				if(seg[pref] == 50005)
					cur = pref ^ 1;
				else
					cur = pref;
			}
			cur ^= v;
			int k = v >> (i + 1);
			if(mpScore[x].count(k))
				mpScore[x][k] = min(mpScore[x][k], cur);
			else
				mpScore[x][k] = cur;
		}
		for(auto [i, w]: child[x])
			if(i != p) {
				dist[i] = dist[x] ^ w;
				dfs(dfs, i, x);
				if(mpScore[i].size() > mpScore[x].size())
					swap(mpScore[x], mpScore[i]);
				for(auto [k, v]: mpScore[i]) {
					if(mpScore[x].count(k))
						mpScore[x][k] = min(mpScore[x][k], v);
					else
						mpScore[x][k] = v;
				}
			}
		for(int i=1;i<21;i++)
			minScore[x][i] = (mpScore[x].count(v>>i)?mpScore[x][v>>i]:50005);
		for(int i=v;i;i>>=1)
			if(seg[i] == x)
				seg[i] = 50005;
		post[x] = cnt;
	};
	dfs(dfs, 0, -1);
}

int minimum_energy(int U, int V) {
	int layer;
	for(layer=0;layer<21;layer++) {
		if(par[U][layer] == par[V][layer])
			break;
	}
	if(layer == 0)
		return 0;
	return max(minScore[par[U][layer-1]][layer],minScore[par[V][layer-1]][layer]);
}

Let $$$f_i(p)$$$ be the cost function when $$$C[j]$$$ is replaced by $$$1$$$ if $$$C[j] \gt i$$$ and $$$0$$$ otherwise, and let $$$f(p)$$$ be the original cost function. Note $$$f(p) = \sum_{i=0}^{99} f_i(p)$$$.

$$$f_i(p)$$$ is the sum of the $$$k_i$$$ largest distances from $$$p$$$ to the cars, for some constant $$$k_i$$$. It can thus be shown that $$$f_i(p)$$$ is convex since the distance to each car is a convex function. Hence $$$f$$$ is convex and we can apply ternary search. This is still too slow as $$$N \leq 10^7$$$.

To speedup, note that we can compute $$$f_i(p)$$$ by binary searching for the distance $$$d$$$, such that $$$k_i$$$ cars are further away than $$$d$$$ from point $$$p$$$. Once we have $$$d$$$, compute $$$L$$$ to $$$R$$$ such that the cars far enough from $$$p$$$ have index $$$ \lt L$$$ or $$$ \gt R$$$, and find the sum of distances for these cars. This runs in $$$O(N + 100 \log N \log^2 X)$$$.

#include "gather.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 3;
int car_gathering(int N, std::vector<int> X, std::vector<int> C) {
	vector<long long> pre(N+1,0);
	vector<int> pos(100);
	for(int i=0;i<100;i++)
		pos[i] = upper_bound(C.begin(),C.end(),i)-C.begin();
	for(int i=0;i<N;i++)
		pre[i+1] = pre[i] + X[i];
	auto comp1 = [&N,&X,&pre](int v, int p) {
		// >= v elements, dist <= d
		long long l = -1, h = 10LL*INF;
		while(h - l > 1) {
			long long m = l + (h - l) / 2;
			int lft = (p >= m - INF ? lower_bound(X.begin(), X.end(), p - m) - X.begin() : 0);
			int rgt = (p <= INF - m ? upper_bound(X.begin(), X.end(), p + m) - X.begin() : N);
			if(rgt - lft >= v)
				h = m;
			else
				l = m;
		}
		int lft = (p >= h - INF ? lower_bound(X.begin(), X.end(), p - h) - X.begin() : 0);
		int rgt = (p <= INF - h ? upper_bound(X.begin(), X.end(), p + h) - X.begin() : N);
		return (1LL * p * lft - pre[lft] + (pre[N] - pre[rgt]) - 1LL * p * (N - rgt) + 1LL * (rgt - lft - v) * h);
	};
	auto compAll = [&pos,&comp1](int p) {
		long long ans = 0;
		for(auto x: pos)
			ans += comp1(x, p);
		return ans;
	};
	// smallest st f(x) <= f(x+1)
	int l = -INF, h=INF;
	while(h - l > 1) {
		int m = l + (h - l) / 2;
		if(compAll(m) <= compAll(m+1))
			h = m;
		else
			l = m;
	}
	return h;
}

Let the "layer" of a node be its distance from 0, and its parent be any parent in the BFS tree. Let the weight of an edge be the maximum distance of one endpoint to node 0.

The main idea is this: Fix the lowest species encountered, L, and build a psuedo-Minimum Spanning Tree using just the nodes at "layer" $$$L$$$. Formally, define the distance between two nodes of "layer" $$$L$$$ as the minimum weight of a path that doesn't pass through nodes in "layer" $$$L-1$$$, where the weight of a path is the maximum weight of edges it passes through. Then, we will ensure that the distance between any two nodes is the same in both the psuedo-MST and the original graph.

If we can build this psuedo-MST, then we can find an ancestor of $$$A$$$ and an ancestor of $$$B$$$ on layer $$$L$$$, and calculate their distance. Doing so for all $$$L$$$ will solve the bugaboo.

To build the psuedo-MST, we will observe that we only need the following edges:

• $$$(u, v)$$$ where $$$u$$$ and $$$v$$$ are in layer $$$L$$$
• $$$(par[u], v)$$$ where $$$u$$$ is in layer $$$L+1$$$ and $$$v$$$ is in layer $$$L$$$
• $$$(par[u], par[v])$$$, where $$$(u, v)$$$ is an edge in the MST of layer $$$L+1$$$

Therefore we build a psuedo-MST using these edges.

Regarding complexity: The total number of edges of the first two types is equal to $$$M$$$. The third type only has $$$(\text{# of nodes in layer L+1}) - 1$$$ edges, which is $$$\leq N$$$ when we sum over all layers, so this algorithm runs in $$$O(N \alpha(N))$$$ (assuming $$$N=M$$$).

Funny thing: I found this solution in-contest, and it took me several additional minutes to realise it was $$$N+M$$$ and not $$$N^2+M$$$.

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

struct ufds {
	vector<int> par, sz;
	ufds(int n): sz(n,1), par(n) {
		iota(par.begin(),par.end(),0);
	}
	int findSet(int x) {
		if(par[x] == x)
			return x;
		return par[x] = findSet(par[x]);
	}
	bool unite(int x, int y) {
		x = findSet(x);
		y = findSet(y);
		if(x == y)
			return 0;
		if(sz[x] > sz[y])
			swap(x, y);
		sz[y] += sz[x];
		par[x] = y;
		return 1;
	}
};

int min_distinct(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
	queue<int> q;
	int dist[N], par[N];
	vector<int> adj[N];
	vector<int> nodes[N];
	memset(dist,-1,sizeof(dist));
	dist[0] = 0;
	q.push(0);
	for(int i=0;i<M;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	while(q.size()) {
		int x = q.front();
		nodes[dist[x]].push_back(x);
		q.pop();
		for(auto y: adj[x])
			if(dist[y] == -1) {
				dist[y] = dist[x] + 1;
				par[y] = x;
				q.push(y);
			}
	}
	ufds u(N);
	vector<tuple<int,int,int>> prv;
	int ans = N;
	int orig = max(dist[A], dist[B]);
	for(int h=N;h--;) {
		int sz = nodes[h].size();
		if(sz == 0)
			continue;
		if(dist[A] > h)
			A = par[A];
		if(dist[B] > h)
			B = par[B];
		if(A == B)
			ans = min(ans, orig - h);
		vector<tuple<int,int,int>> nw;
		for(auto x: nodes[h])
			for(auto y: adj[x])
				if(dist[x] == dist[y] && u.unite(x, y)) {
					nw.push_back({h, x, y});
					if(u.findSet(A) == u.findSet(B))
						ans = min(ans, orig - h);
				}
		for(auto x: nodes[h])
			for(auto y: adj[x])
				if(dist[y] > dist[x] && u.unite(x, par[y])) {
					nw.push_back({h+1, x, par[y]});
					if(u.findSet(A) == u.findSet(B))
						ans = min(ans, max(orig, h+1) - h);
				}
		for(auto [w, x, y]: prv) {
			x = par[x];
			y = par[y];
			if(u.unite(x, y)) {
				nw.push_back({w, x, y});
				if(u.findSet(A) == u.findSet(B))
					ans = min(ans, max(orig, w) - h);
			}
		}
		prv = nw;
		nw.clear();
	}
	return ans+1;
}

As the first problem in the contest, I read this problem first. The problem looked quite interesting, so I spent a bit of time on it before reading the other problems. I ended up immediately guessing the correct greedy, and submitted code that got 83 points, which very quickly became 100 points. I solved this before even attempting to think about the other problems.

The most restrictive element in $$$P$$$ is the one with the largest $$$P[i]$$$. It needs to be either the element with the largest $$$A[i]$$$ or largest $$$B[i]$$$. On the other hand, the least restrictive elements in $$$A$$$ and $$$B$$$ are the ones with the largest $$$A[i]$$$ and $$$B[i]$$$ respectively, since they can have any $$$P[i]$$$ and still fulfill the condition. Since both of these indices give the same use, we should focus on $$$P[i] - i$$$ to determine which one gets the largest $$$P[i]$$$. Clearly, to minimise $$$P[i] - i$$$, we should choose the larger of the 2. Now, notice that we have 1 less element to deal with and a similar problem left on our hands. We can repeat this process again with the new largest $$$A[i]$$$ and $$$B[i]$$$.

This motivates the full greedy solution: Assign the values of $$$P$$$ to the indices in decreasing order of $$$P[i]$$$. While there are still unchosen elements, let $$$x$$$ be the index with the largest $$$A[x]$$$ amongst all unchosen indices, and let $$$y$$$ be the index with the largest $$$B[y]$$$ amongst all unchosen indices. If $$$x = y$$$, assign the currently largest unused value of $$$P[i]$$$ to $$$x$$$. Otherwise, pick the larger of the 2 and assign the largest unused $$$P[i]$$$ to it.

Let's look at the sample testcase for an example. We have $$$A = [3, 0, 4, 1, 2]$$$, $$$B = [0, 3, 2, 4, 1]$$$. As our algorithm goes, we first find the element that we will assign $$$P[i] = 4$$$ to. $$$x = 2$$$ and $$$y = 3$$$, since $$$A[2] = 4$$$ and $$$B[3] = 4$$$. $$$y$$$ is bigger, so we set $$$P[y] = 4$$$ (i.e. $$$P[3] = 4$$$).

On the next run, we are assigning $$$P[i] = 3$$$. Now, $$$x = 2$$$ and $$$y = 1$$$, since $$$A[0] = 4$$$ and $$$B[1] = 3$$$. Now $$$x$$$ is bigger, so we set $$$P[2] = 3$$$.

By continuing the process, every element will get assigned a value.

This algorithm can be proven to work using a simple exchange argument. At any step in the algorithm, since there are only 2 valid choices for the index that takes on $$$P[i]$$$ ($$$x$$$ and $$$y$$$), if the algorithm chose one of them and it was unoptimal, the other one must be used in an optimal solution. However the rest of the algorithm continues as usual and in the end, swapping the values of $$$P[x]$$$ and $$$P[y]$$$ that we had would not make the result any worse. More formal writing is left as an exercise to the reader.

To implement this, we sort the indices by $$$A[i]$$$ and $$$B[i]$$$ in 2 separate arrays, and maintain 2 pointers pointing to the largest element with an undetermined $$$P[i]$$$. We also keep an array representing whether each index has its $$$P[i]$$$ determined yet.

Note that the sorting here needs to be done using counting sort, since permutations can be sorted in $$$O(N)$$$ and the problem setter successfully set tight enough limits ($$$N$$$ up to 5 million), to the point where std::sort fails the time limit. The overall time complexity should be $$$O(N)$$$.

My code in contest is as follows:

#include "exam.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j += (m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k += (m<h?1:-1))
#define pll pair<ll, ll>

int minimum_dissatisfaction(int N, vector<int> A, vector<int> B) {
	ll n = N;
	pll a[n], b[n];
	iloop(0, n) a[n - A[i] - 1] = {A[i], i}, b[n - B[i] - 1] = {B[i], i};
	ll ca = 0, cb = 0, cans = 0;
	bool used[n];
	memset(used, 0, sizeof(used));
	iloop(0, n) {
		while (ca < n && used[a[ca].second]) ca++;
		while (cb < n && used[b[cb].second]) cb++;
		if (cb == n || (ca < n && a[ca].second > b[cb].second)) {
			used[a[ca].second] = 1;
			cans = max(cans, (n-i) - (a[ca].second + 1));
		}
		else {
			used[b[cb].second] = 1;
			cans = max(cans, (n-i) - (b[cb].second + 1));
		}
	}
	return cans;
}

This problem was quite interesting, having 2 parts which I could not determine whether they were related. After the contest, errorgorn informed me that the rankings and scores used in the statement (go check it out) were actually taken from last year's IOI. After some digging, here are the actual sources of the scores:

• All 4 members on the scoreboard with country "Singapore" correspond to last year's Korea team.
• The first 2 members of team "Malaysia" correspond to the 2 gold medalists from last year's Singapore team.
• The last member of team "Malaysia" corresponds to Malaysia team's gold medalist last year.
• The 2 members of team "Indonesia" are from team Hungary and Taiwan respectively.

This was interesting to say the least. The problem itself is not bad, and the parts felt similar yet different enough in idea to make this a cool problem.

For the rest of the problem, define $$$f_i(x)$$$ as the number of people up to person $$$i$$$ (zero-indexed) with rank $$$x$$$. For convenience, let $$$f_{-1}(x) = 0$$$ for all $$$x$$$.

We shall start with part (a). The first observation is as follows: If person $$$i$$$ with country rank $$$x$$$ has some person $$$j$$$ in front of them who must be in the same country, then there must be some person $$$i$$$ with country rank $$$x-1$$$ in front of them who must be in the same country.

A quick idea of the proof would be that one can swap the country of person $$$i$$$ and some other people in the same country to change person $$$j$$$. For the formal proof, suppose otherwise. Then there must be at least 2 possibilities of persons $$$a$$$ and $$$b$$$, both with country rank $$$x-1$$$. Suppose without loss of generality person $$$i$$$ is in the same country as person $$$a$$$ in some construction. Then consider swapping the countries of everyone in person $$$a$$$'s country with a worse rank that $$$x-1$$$ and everyone in person $$$b$$$'s country with a worse rank than $$$x-1$$$. One still gets a valid configuration of countries, however person $$$i$$$ has now switched countries and has a different person $$$j$$$ in front of them, a contradiction since person $$$j$$$ is determined.

To continue, consider processing person $$$i$$$ with country rank $$$x$$$ and determining which people in front of them must be from the same country as them. From the observation, it is sufficient to determine the person with rank $$$x-1$$$ (if there exists any) since we can mark them as the same country and in the end, count the number of people connected together (this calls for DSU / UFDS to keep track of who must be together). Consider $$$f_{i-1}(x-1) - f_{i-1}(x)$$$, which is the number of people with country rank $$$x-1$$$ which have not been picked by someone with a country rank $$$x$$$. It is guaranteed to be at least 1 since a valid ranking must exist. If $$$f_{i-1}(x-1) - f_{i-1}(x) \gt 1$$$, there are at least 2 possible people with country rank $$$x-1$$$ who are in the same country. Thus $$$f_{i-1}(x-1) - f_{i-1}(x) = 1$$$ is necessary.

It is, however, not sufficient. Consider a case where the country ranks are $$$[0, 0, 1, 1]$$$. For the last person, $$$f_2(0)-f_2(1)=2-1=1$$$, however it is still possible for them to be in the same country as either one of the 0s. After some thinking and/or guessing, we obtain that $$$f_{i-1}(x-1) - f_{i-1}(x) = 1$$$ must hold, and the previous occurrence of country rank $$$x-1$$$ must be closer than the previous occurrence of country rank $$$x$$$. Another way of looking at this is that if $$$f_{i-1}(x-1) - f_{i-1}(x)$$$ ever exceeds 1, anyone following with country rank $$$x$$$ will not have a guaranteed partner until $$$f_{i-1}(x-1) - f_{i-1}(x)$$$ "resets" to 0.

As mentioned earlier, we can use a UFDS / DSU to maintain relationships of who is in the same country. In my code prog denotes $$$f_{i-1}(x) - f_{i-1}(x+1)$$$ while rs denotes whether the values of prog have been reset to 0. There is the special case of someone with country rank $$$0$$$.

#include "country.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j += (m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k += (m<h?1:-1))
#define pll pair<ll, ll>
ll par[1000005], sz[1000005];
ll n, cans, tmp;
ll find(ll x) {
	return (x == par[x] ? x : par[x] = find(par[x]));
}
void merge(ll x, ll y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	par[y] = x;
	sz[x] += sz[y];
}
long long count_same_country(int N, vector<int> country_rank) {
	n = N, cans = 0;
	ll prog[n], a[n], prv[n];
	bool rs[n];
	iloop(0, n) a[i] = country_rank[i], par[i] = i, sz[i] = 1, prog[i] = 0, rs[i] = 1;
	iloop(0, n) {
		if (a[i]) {
			if (prog[a[i]-1] == 1 && rs[a[i]-1]) merge(i, prv[a[i]-1]);
			prog[a[i]-1]--;
			if (prog[a[i]-1] == 0) rs[a[i]-1] = 1;
		}
		prog[a[i]]++;
		if (prog[a[i]] == 2) rs[a[i]] = 0;
		prv[a[i]] = i;
	}
	iloop(0, n) if (par[i] == i) cans += sz[i] * (sz[i] - 1) / 2;
	return cans;
}

For part (b), it helps to consider when 2 people cannot be in the same country. There are 3 possibilities:

• The person in front has a country rank at least that of the person behind.
• There are not enough people in between that can form the chain of people in the same country with successive country ranks.
• The person in front is forced to be connected to someone else instead of that person, like in the scenario $$$[0, 1, 0, 1]$$$ where the last person cannot be with the first person.

The first 2 cases seem reasonable to handle. The first case contributes a lower bound to what country ranks a new person must be to be in the same country, while the second case seems to contribute an upper bound. It turns out that the third case also contributes a lower bound!

The third case borrows a similar idea from part (a): When $$$f_{i}(x-1) - f_{i}(x) = 0$$$, everyone up to that point with country rank $$$x-1$$$ is forced to have the next person from the same country to be indexed at most $$$i$$$. Usefully, $$$f_i(x)$$$ is monotone decreasing on $$$x$$$.

It can be shown (with many details, unfortunately not by me) that these conditions are necessary and sufficient for 2 people to be forced into different countries. In contest, I first implemented a $$$O(N^2)$$$ solution to verify the claim (it gave 21 points on (b)). Processing everyone in increasing order of rank, I assign everyone a range [lh, rh] where a person can potentially share a country with someone new being processed if the country rank of the new person lies in the range. For the 3 possibilities,

• At the start lh = rh = country_rank[i]+1
• If some person with country rank rh shows up, increase rh by 1
• If the count of $$$f_i(lh) - f_i(lh+1)$$$ reaches 0, increment lh

This is easier to check from the perspective of the new person being processed:

• For anyone with rh as the current country rank, increment it
• If the increase in country rank results in $$$f_i(lh) - f_i(lh+1)$$$ where lh + 1 = country_rank[i], increment all such $$$lh$$$

Then for each person, the number of people in front who cannot be in the same country is the number of people whose range does not include the country rank.

The code for this partial solution is as follows:

long long count_diff_country(int N, vector<int> country_rank) {
	ll n = N, cans = 0;
	ll prog[n], a[n], lh[n], rh[n];
	iloop(0, n) a[i] = country_rank[i], prog[i] = 0;
	iloop(0, n) {
		jloop(0, i) {
			if (lh[j] > a[i] || rh[j] < a[i]) cans++;
			if (rh[j] == a[i]) rh[j]++;
		}
		if (a[i]) {
			prog[a[i]-1]--;
			if (!prog[a[i]-1]) jloop(0, i) if (lh[j] == a[i]) lh[j]++;
		}
		prog[a[i]]++;
		lh[i] = rh[i] = a[i]+1;
	}
	return cans;
}

To speed this up, notice that we only care about the values of $$$lh$$$ and $$$rh$$$ and not about the indices that correspond to them. We can thus use a data structure such as a segment tree to store these values. The AC code for this part is as follows:

ll seg[2][2000005];
void upd(ll X, ll V, ll id) {
	for (seg[id][X += n] += V; X > 1; X >>= 1) seg[id][X>>1] = seg[id][X] + seg[id][X^1];
}
ll qu(ll S, ll E, ll id) {
	E++;
	ll res = 0;
	for (S += n, E += n; S != E; S >>= 1, E >>= 1) {
		if (S&1) res += seg[id][S++];
		if (E&1) res += seg[id][--E];
	}
	return res;
}
long long count_diff_country(int N, vector<int> country_rank) {
	n = N, cans = 0;
	ll prog[n], a[n];
	iloop(0, 2*n) seg[0][i] = seg[1][i] = 0;
	iloop(0, n) a[i] = country_rank[i], prog[i] = 0;
	iloop(0, n) {
		cans += qu(a[i]+1, n-1, 0);
		cans += qu(0, a[i]-1, 1);
		tmp = qu(a[i], a[i], 1);
		upd(a[i], -tmp, 1);
		upd(a[i]+1, tmp, 1);
		if (a[i]) {
			prog[a[i]-1]--;
			//if (!prog[a[i]-1]) jloop(0, i) if (lh[j] == a[i]) lh[j]++;
			if (!prog[a[i]-1]) {
				tmp = qu(a[i], a[i], 0);
				upd(a[i], -tmp, 0);
				upd(a[i]+1, tmp, 0);
			}
		}
		prog[a[i]]++;
		upd(a[i]+1, 1, 0);
		upd(a[i]+1, 1, 1);
	}
	return cans;
}

You may try to see how the 2 pieces of code here basically do the same thing. This now runs in $$$O(N\log N)$$$

This problem was quite cool. Initially, it reminded me of a certain algorithm that turns out was part of the intended solution, but I couldn't finish the problem with it. Fortunately the problem has many ways to go about solving. The other FC (literalchild) reportedly used a different solution.

Also I once said that XOR is my favourite operation, and it still is.

The minimum maximum cost of steps suggests the use of a minimum spanning tree (MST) on the steps. Once the MST is built, one can use methods such as Kruskal Reconstruction Tree or binary lifting (my preference) to query for path maximums on the MST. This is where the idea of using Boruvka's algorithm first appeared, since someone once told me that Boruvka's is good for MSTs on graphs with many edges; unfortunately, I could not finish the problem using it although the intended solution apparently uses it.

I first coded out the direct MST solution, adding all steps between ancestors and nodes to the graph that would be MST'ed on.

#include "teleport.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j += (m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k += (m<h?1:-1))
#define pll pair<ll, ll>
#define INF 2000000000000000LL
ll n, p[50005], a[50005], x, y, z;
vector<ll> adj[50005];
vector<pair<ll, pll>> ae;
vector<pll> adj2[50005];
ll twok[17][50005], twok2[17][50005], dp[50005], cc;
ll par[50005], sz[50005];
ll find(ll x) {
	return (par[x] == x ? x : par[x] = find(par[x]));
}
ll merge(ll x, ll y) {
	x = find(x), y = find(y);
	if (x == y) return 0;
	if (sz[x] < sz[y]) swap(x, y);
	par[y] = x;
	sz[x] += sz[y];
	return 1;
}
void dfs(ll nd, ll pr) {
	for (auto it : adj[nd]) if (it != pr) {
		a[it] ^= a[nd];
		dfs(it, nd);
	}
}
void dfs2(ll nd, ll pr) {
	twok[0][nd] = pr;
	iloop(1, 17) {
		if (twok[i-1][nd] == -1) break;
		twok[i][nd] = twok[i-1][twok[i-1][nd]];
		if (twok[i][nd] != -1) twok2[i][nd] = max(twok2[i-1][nd], twok2[i-1][twok[i-1][nd]]);
	}
	for (auto it : adj2[nd]) if (it.second != pr) {
		dp[it.second] = dp[nd] + 1;
		twok2[0][it.second] = it.first;
		dfs2(it.second, nd);
	}
}
ll lca(ll x, ll y) {
	ll cans = 0;
	if (dp[x] < dp[y]) swap(x, y);
	iloop(16, -1) if (dp[x] - dp[y] >= 1<<i) {cans = max(cans, twok2[i][x]); x = twok[i][x];}
	if (x == y) return cans;
	iloop(16, -1) if (twok[i][x] != twok[i][y]) {
		cans = max({cans, twok2[i][x], twok2[i][y]});
		x = twok[i][x], y = twok[i][y];
	}
	cans = max({cans, twok2[0][x], twok2[0][y]});
	return cans;
}
void init(int N, vector<int> P, vector<int> W) {
	n = N;
	memset(twok, -1, sizeof(twok));
	p[0] = -1, a[0] = 0;
	iloop(1, n) {
		p[i] = P[i], a[i] = W[i];
		adj[p[i]].push_back(i);
	}
	dfs(0, -1);
	ae.clear();
	iloop(0, n) {
		x = p[i];
		while (x != -1) {
			ae.push_back({a[x] ^ a[i], {x, i}});
			x = p[x];
		}
	}
	sort(ae.begin(), ae.end());
	cc = 0;
	iloop(0, n) par[i] = i, sz[i] = 1;
	for (auto it : ae) {
		if (merge(it.second.first, it.second.second)) {
			cc++;
			adj2[it.second.first].push_back({it.first, it.second.second});
			adj2[it.second.second].push_back({it.first, it.second.first});
			//cout << it.first << " " << it.second.first << " " << it.second.second << endl;
			if (cc == n-1) break;
		}
	}
	dfs2(0, -1);
}

int minimum_energy(int U, int V) {
	x = U, y = V;
	return lca(x, y);
}

This got 20 points In $$$O(N^2\log N)$$$.

Next, I was eyeing the 28 points subtask $$$W \lt 128$$$ along with the $$$9$$$ points from the easier $$$W \le 1$$$. This suggests that having a small number of possible edge weights (and thus path costs) may mean something. Using this, I obtained an observation:

Given a node, if 2 of its ancestors have the same path cost from it, there exists an MST where at most 1 of these steps is included.

This is immediate after noticing from XOR properties that the step cost between the 2 ancestors must be 0.

Using this, I come up with the following algorithm: for each node, find all unique path costs to an ancestor, then include only 1 of each such path cost in the computation of the MST. There are only $$$NW$$$ path costs in the MST computation now, so the time complexity is $$$O(NW\log{NW})$$$. To implement, note that XOR properties allow us to simply store the parents by their prefix XORs from the root. The modified dfs function is as follows, with the part in the main computation function adding edges removed:

vector<ll> prv[130];
void dfs(ll nd, ll pr) {
	iloop(0, 128) if (prv[i].size()) ae.push_back({i^a[nd], {prv[i].back(), nd}});
	prv[a[nd]].push_back(nd);
	for (auto it : adj[nd]) if (it != pr) {
		a[it] ^= a[nd];
		dfs(it, nd);
	}
	prv[a[nd]].pop_back();
}

This motivates the idea that not all edges may be useful. After deliberating on this thought, I obtain a stronger version of the previous observation that can be used to solve the problem:

Given a node, if the path costs to 2 of its ancestors have the same most significant bit, there is an MST solution with at most 1 of these steps. In particular, the step with the larger cost should not be needed.

This is immediate after noticing that the path costs between the 2 ancestors must, by XOR properties, have a smaller most significant bit and thus smaller value.

If we only include steps from nodes to their ancestors which, out of all other such steps sharing the same most significant bit, is minimal, there will be only $$$O(N\log W)$$$ edges to check for in the MST. This should be fast enough.

To pull this off, I use a binary trie to store all values of the prefix XORs from the root. At every node, the code checks through the binary trie to find the minimal value for each most significant bit, as well as which node it is from. This is done as such:

• If the current traversal has deviated from the prefix XOR to the node, the most significant bit has been passed and thus it is optimal to minimise the XOR, i.e. match the bits in the prefix XOR to the node whenever possible.
• If the current traversal perfectly matches the prefix XOR to the node, visit both children in the trie.

This gets all $$$O(\log W)$$$ ancestors. After that, just run the MST as per usual.

The code with the trie and the modified dfs function is as follows. The gt flag in the trav (traversal) function in the trie is 1 if the path has deviated from the prefix XOR to the node and 0 otherwise.

vector<ll> useful;
struct node {
	node *l, *r;
	vector<ll> vs;
	ll cn = 0, dpt;
	node (ll dpn) {
		dpt = dpn;
		if (dpt == g) return;
		l = new node(dpn + 1);
		r = new node(dpn + 1);
	}
	void add(ll X, ll V) {
		cn++;
		if (dpt == g) {
			vs.push_back(V);
			return;
		}
		if (X%2 == 0) l->add(X>>1, V);
		else r->add(X>>1, V);
	}
	void rm(ll X) {
		cn--;
		if (dpt == g) {
			vs.pop_back();
			return;
		}
		if (X%2 == 0) l->rm(X>>1);
		else r->rm(X>>1);
	}
	void trav(ll V, bool gt) {
		if (cn == 0) return;
		if (dpt == g) {
			useful.push_back(vs.back());
			return;
		}
		if (gt) {
			if (V%2 == 0) {
				if (l->cn) l->trav(V>>1, 1);
				else r->trav(V>>1, 1);
			}
			if (V%2 == 1) {
				if (r->cn) r->trav(V>>1, 1);
				else l->trav(V>>1, 1);
			}
			return;
		}
		if (V%2 == 0) {
			l->trav(V>>1, 0);
			r->trav(V>>1, 1);
		}
		else {
			l->trav(V>>1, 1);
			r->trav(V>>1, 0);
		}
	}
} *root;
void dfs(ll nd, ll pr) {
	useful.clear();
	ll cv = 0, ctm = a[nd];
	iloop(0, g) {cv = cv*2 + (ctm%2); ctm >>= 1;}
	root->trav(cv, 0);
	//for (auto it : useful) cout << nd << ":" << it << endl;
	for (auto it : useful) ae.push_back({a[it]^a[nd], {it, nd}});
	root->add(cv, nd);
	for (auto it : adj[nd]) if (it != pr) {
		a[it] ^= a[nd];
		dfs(it, nd);
	}
	root->rm(cv);
}

This runs in $$$O(N\log{W}\log{N\log{w}})$$$.