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://codeforces.me/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://codeforces.me/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;
}