2228FUnreviewedunratedGPT-5.5 (high)

Momoyo and the Network

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

binary search dfs and similar divide and conquer dp trees

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Binary search the answer $X$ . For a fixed $X$ , don’t try to optimize anything — just ask: is there a path whose every produced component has weight at least $X$ ? Monotonicity is doing the heavy lifting here.

For an edge $uv$ , define $c(u,v)$ as the weight of the component containing $u$ after deleting edge $uv$ . Then endpoint conditions on a chosen path are just $c(v_0,v_1)\ge X$ and $c(v_k,v_{k-1})\ge X$ .

If a path passes through vertex $v$ using neighbors $p$ and $q$ , the component of $v$ after removing both path edges has weight

c(v,p)+c(v,q)-S,

where $S=\sum a_i$ . So the local compatibility condition is

c(v,p)+c(v,q)\ge S+X.

Now the feasibility check becomes: find the longest path in the tree where endpoints satisfy $c\ge X$ , and every consecutive pair of edges through a vertex satisfies the compatibility inequality. If the longest such path has length at least $k$ , then a length exactly $k$ subpath also works, because removing fewer edges only merges positive-weight components at the ends.

Use reroot DP on directed edges. Let $dp_{u\to v}$ be the longest valid half-path ending with edge $u\to v$ , with the condition at $v$ not checked yet. Then

dp_{u\to v}=\max\left([c(u,v)\ge X],\ 1+\max_{p\ne v,\ c(u,p)+c(u,v)\ge S+X} dp_{p\to u}\right).

At each vertex, sort neighbors by $c(v,\cdot)$ and use prefix top-two $dp$ values to answer all transitions in linear time.

Binary search the minimum component weight

Let

S=\sum_{i=1}^n a_i.

If we can make every component have weight at least $X$ , then we can also do it for any smaller value. So the answer is found by binary search on $X$ .

Also, after removing exactly $k$ edges, there are $k+1$ components, hence

X\le \left\lfloor \frac{S}{k+1}\right\rfloor.

The real problem is the feasibility check for a fixed $X$ .

Edge-side weights

For an edge $uv$ , define

c(u,v)=\text{weight of the component containing }u\text{ after deleting }uv.

These values are easy to compute from subtree sums after rooting the tree anywhere.

Consider a candidate path

v_0,v_1,\dots,v_\ell.

For an endpoint, say $v_0$ , after deleting edge $v_0v_1$ , its component weight is exactly

c(v_0,v_1).

So endpoints require

c(v_0,v_1)\ge X, \qquad c(v_\ell,v_{\ell-1})\ge X.

For an internal vertex $v_i$ , with path-neighbors $v_{i-1}$ and $v_{i+1}$ , its component is everything except the two branches going through those two neighbors. Therefore its weight is

c(v_i,v_{i-1})+c(v_i,v_{i+1})-S.

Thus the internal condition is

c(v_i,v_{i-1})+c(v_i,v_{i+1})\ge S+X.

That is the key local condition. Once you see this, the tree stops looking scary and starts behaving.

Why longest path is enough

For fixed $X$ , suppose we find a valid path of length $L\ge k$ . Then any contiguous subpath of length exactly $k$ is also valid.

Internal vertices of the subpath have the same two removed incident edges as before. Endpoints of the subpath may have fewer removed edges than they had in the longer path, so their components only get larger. Since all weights are positive, nothing breaks.

So feasibility means:

Is there a valid path of length at least $k$ ?

Directed-edge DP

Define $dp_{u\to v}$ as the maximum length of a valid half-path ending with directed edge $u\to v$ .

More precisely, the path ends at $v$ , the previous vertex is $u$ , the far endpoint is already valid, and all internal vertices up to $u$ are already valid. Vertex $v$ is not checked yet.

There are two ways to form $dp_{u\to v}$ :

Start the path with just edge $uv$ . Then $u$ is an endpoint, so we need
$c(u,v)\ge X.$
Extend some half-path ending at $u$ through a neighbor $p\ne v$ . Then $u$ becomes internal, so we need
$c(u,p)+c(u,v)\ge S+X.$

Therefore

dp_{u\to v}= \max\left( [c(u,v)\ge X],\ 1+\max_{\substack{p\in N(u),\ p\ne v\\ c(u,p)+c(u,v)\ge S+X}} dp_{p\to u} \right).

We use $0$ for impossible states.

A full valid path ending at $v$ through $u$ exists if additionally

c(v,u)\ge X,

and then its length is $dp_{u\to v}$ .

Rerooting order

Root the tree at $1$ .

First compute all states from child to parent using a bottom-up pass. For $dp_{u\to parent(u)}$ , we only need incoming states from children of $u$ , which are already known.

Then compute states from parent to child using a top-down pass. When processing vertex $u$ , all incoming states $dp_{p\to u}$ from every neighbor $p$ are known, so we can compute outgoing states $dp_{u\to child}$ .

Classic reroot DP. Nothing fancy, just don’t trip over directions.

Fast transitions at one vertex

At a vertex $u$ , for every outgoing neighbor $v$ , we need

\max dp_{p\to u}

over neighbors $p\ne v$ satisfying

c(u,p)\ge S+X-c(u,v).

Sort neighbors of every vertex once by $c(u,\cdot)$ in descending order.

During one feasibility check, build prefix best and second-best $dp$ values for each vertex. The second-best is needed to exclude $p=v$ without doing ugly hacks.

Since thresholds are monotonic while scanning sorted neighbors, all outgoing transitions of one vertex can be processed in

O(\deg u).

So one feasibility check costs

O(n),

after the initial sorting.

The binary search gives total complexity

O(n\log S)

per test set, plus sorting adjacency lists once:

O(n\log n).

Memory is

O(n).

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct Item {
    int to, eid, rev;
    ll val;          // c(current vertex, to)
    int dp;          // dp[to -> current vertex]
    int pref1, pref2, prefIdx;
};

int main() {
    setIO();

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

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

        vector<int> U(n - 1), V(n - 1);
        vector<vector<pair<int,int>>> raw(n);
        for (int i = 0; i < n - 1; i++) {
            cin >> U[i] >> V[i];
            --U[i], --V[i];
            raw[U[i]].push_back({V[i], i});
            raw[V[i]].push_back({U[i], i});
        }

        vector<int> parent(n, -2), parentEdge(n, -1), order;
        order.reserve(n);
        parent[0] = -1;

        vector<int> st = {0};
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            order.push_back(u);
            for (auto [v, eid] : raw[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                parentEdge[v] = eid;
                st.push_back(v);
            }
        }

        vector<ll> sub = a;
        for (int i = n - 1; i > 0; i--) {
            int u = order[i];
            sub[parent[u]] += sub[u];
        }

        vector<vector<Item>> g(n);
        for (int eid = 0; eid < n - 1; eid++) {
            int u = U[eid], v = V[eid];
            ll cuv, cvu;
            if (parent[v] == u) {
                cuv = total - sub[v];
                cvu = sub[v];
            } else {
                cvu = total - sub[u];
                cuv = sub[u];
            }
            g[u].push_back({v, eid, -1, cuv, 0, 0, 0, -1});
            g[v].push_back({u, eid, -1, cvu, 0, 0, 0, -1});
        }

        vector<int> posU(n - 1), posV(n - 1), parPos(n, -1);
        for (int u = 0; u < n; u++) {
            sort(g[u].begin(), g[u].end(), [](const Item& x, const Item& y) {
                return x.val > y.val;
            });
            for (int i = 0; i < (int)g[u].size(); i++) {
                int eid = g[u][i].eid;
                if (U[eid] == u) posU[eid] = i;
                else posV[eid] = i;
            }
        }

        for (int u = 0; u < n; u++) {
            for (int i = 0; i < (int)g[u].size(); i++) {
                int eid = g[u][i].eid;
                if (U[eid] == u) g[u][i].rev = posV[eid];
                else g[u][i].rev = posU[eid];

                if (g[u][i].to == parent[u]) parPos[u] = i;
            }
        }

        auto feasible = [&](ll X) -> bool {
            for (int u = 0; u < n; u++) {
                for (auto &e : g[u]) e.dp = 0;
            }

            auto buildPrefix = [&](int u) {
                int best1 = 0, best2 = 0, idx1 = -1;
                for (int i = 0; i < (int)g[u].size(); i++) {
                    int cur = g[u][i].dp;
                    if (cur > best1) {
                        best2 = best1;
                        best1 = cur;
                        idx1 = i;
                    } else if (cur > best2) {
                        best2 = cur;
                    }
                    g[u][i].pref1 = best1;
                    g[u][i].pref2 = best2;
                    g[u][i].prefIdx = idx1;
                }
            };

            auto calcOut = [&](int u, int i, int cnt) -> int {
                int res = (g[u][i].val >= X ? 1 : 0);
                int best = 0;
                if (cnt > 0) {
                    const Item &last = g[u][cnt - 1];
                    best = (last.prefIdx == i ? last.pref2 : last.pref1);
                }
                if (best > 0) res = max(res, best + 1);
                return res;
            };

            // Bottom-up: child -> parent states.
            for (int oi = n - 1; oi >= 1; oi--) {
                int u = order[oi];
                buildPrefix(u);

                int target = parPos[u];
                int d = (int)g[u].size();
                int ptr = d;
                int out = 0;

                for (int i = 0; i <= target; i++) {
                    ll need = total + X - g[u][i].val;
                    while (ptr > 0 && g[u][ptr - 1].val < need) ptr--;
                    if (i == target) {
                        out = calcOut(u, i, ptr);
                        break;
                    }
                }

                Item &e = g[u][target];
                g[e.to][e.rev].dp = out;
            }

            int longest = 0;

            // Top-down: parent -> child states, and check completed paths.
            for (int u : order) {
                buildPrefix(u);

                for (const auto &e : g[u]) {
                    if (e.val >= X) longest = max(longest, e.dp);
                }
                if (longest >= k) return true;

                int d = (int)g[u].size();
                int ptr = d;
                for (int i = 0; i < d; i++) {
                    ll need = total + X - g[u][i].val;
                    while (ptr > 0 && g[u][ptr - 1].val < need) ptr--;

                    int v = g[u][i].to;
                    if (parent[v] == u) {
                        int out = calcOut(u, i, ptr);
                        g[v][g[u][i].rev].dp = out;
                    }
                }
            }

            return longest >= k;
        };

        if (!feasible(1)) {
            cout << -1 << '\n';
            continue;
        }

        ll lo = 1, hi = total / (k + 1);
        while (lo < hi) {
            ll mid = (lo + hi + 1) / 2;
            if (feasible(mid)) lo = mid;
            else hi = mid - 1;
        }

        cout << lo << '\n';
    }

    return 0;
}

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct Item {
    int to, eid, rev;
    ll val;          // c(current vertex, to)
    int dp;          // dp[to -> current vertex]
    int pref1, pref2, prefIdx;
};

int main() {
    setIO();

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

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

        vector<int> U(n - 1), V(n - 1);
        vector<vector<pair<int,int>>> raw(n);
        for (int i = 0; i < n - 1; i++) {
            cin >> U[i] >> V[i];
            --U[i], --V[i];
            raw[U[i]].push_back({V[i], i});
            raw[V[i]].push_back({U[i], i});
        }

        vector<int> parent(n, -2), parentEdge(n, -1), order;
        order.reserve(n);
        parent[0] = -1;

        vector<int> st = {0};
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            order.push_back(u);
            for (auto [v, eid] : raw[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                parentEdge[v] = eid;
                st.push_back(v);
            }
        }

        vector<ll> sub = a;
        for (int i = n - 1; i > 0; i--) {
            int u = order[i];
            sub[parent[u]] += sub[u];
        }

        vector<vector<Item>> g(n);
        for (int eid = 0; eid < n - 1; eid++) {
            int u = U[eid], v = V[eid];
            ll cuv, cvu;
            if (parent[v] == u) {
                cuv = total - sub[v];
                cvu = sub[v];
            } else {
                cvu = total - sub[u];
                cuv = sub[u];
            }
            g[u].push_back({v, eid, -1, cuv, 0, 0, 0, -1});
            g[v].push_back({u, eid, -1, cvu, 0, 0, 0, -1});
        }

        vector<int> posU(n - 1), posV(n - 1), parPos(n, -1);
        for (int u = 0; u < n; u++) {
            sort(g[u].begin(), g[u].end(), [](const Item& x, const Item& y) {
                return x.val > y.val;
            });
            for (int i = 0; i < (int)g[u].size(); i++) {
                int eid = g[u][i].eid;
                if (U[eid] == u) posU[eid] = i;
                else posV[eid] = i;
            }
        }

        for (int u = 0; u < n; u++) {
            for (int i = 0; i < (int)g[u].size(); i++) {
                int eid = g[u][i].eid;
                if (U[eid] == u) g[u][i].rev = posV[eid];
                else g[u][i].rev = posU[eid];

                if (g[u][i].to == parent[u]) parPos[u] = i;
            }
        }

        auto feasible = [&](ll X) -> bool {
            for (int u = 0; u < n; u++) {
                for (auto &e : g[u]) e.dp = 0;
            }

            auto buildPrefix = [&](int u) {
                int best1 = 0, best2 = 0, idx1 = -1;
                for (int i = 0; i < (int)g[u].size(); i++) {
                    int cur = g[u][i].dp;
                    if (cur > best1) {
                        best2 = best1;
                        best1 = cur;
                        idx1 = i;
                    } else if (cur > best2) {
                        best2 = cur;
                    }
                    g[u][i].pref1 = best1;
                    g[u][i].pref2 = best2;
                    g[u][i].prefIdx = idx1;
                }
            };

            auto calcOut = [&](int u, int i, int cnt) -> int {
                int res = (g[u][i].val >= X ? 1 : 0);
                int best = 0;
                if (cnt > 0) {
                    const Item &last = g[u][cnt - 1];
                    best = (last.prefIdx == i ? last.pref2 : last.pref1);
                }
                if (best > 0) res = max(res, best + 1);
                return res;
            };

            // Bottom-up: child -> parent states.
            for (int oi = n - 1; oi >= 1; oi--) {
                int u = order[oi];
                buildPrefix(u);

                int target = parPos[u];
                int d = (int)g[u].size();
                int ptr = d;
                int out = 0;

                for (int i = 0; i <= target; i++) {
                    ll need = total + X - g[u][i].val;
                    while (ptr > 0 && g[u][ptr - 1].val < need) ptr--;
                    if (i == target) {
                        out = calcOut(u, i, ptr);
                        break;
                    }
                }

                Item &e = g[u][target];
                g[e.to][e.rev].dp = out;
            }

            int longest = 0;

            // Top-down: parent -> child states, and check completed paths.
            for (int u : order) {
                buildPrefix(u);

                for (const auto &e : g[u]) {
                    if (e.val >= X) longest = max(longest, e.dp);
                }
                if (longest >= k) return true;

                int d = (int)g[u].size();
                int ptr = d;
                for (int i = 0; i < d; i++) {
                    ll need = total + X - g[u][i].val;
                    while (ptr > 0 && g[u][ptr - 1].val < need) ptr--;

                    int v = g[u][i].to;
                    if (parent[v] == u) {
                        int out = calcOut(u, i, ptr);
                        g[v][g[u][i].rev].dp = out;
                    }
                }
            }

            return longest >= k;
        };

        if (!feasible(1)) {
            cout << -1 << '\n';
            continue;
        }

        ll lo = 1, hi = total / (k + 1);
        while (lo < hi) {
            ll mid = (lo + hi + 1) / 2;
            if (feasible(mid)) lo = mid;
            else hi = mid - 1;
        }

        cout << lo << '\n';
    }

    return 0;
}

View on Codeforces Back to the list