Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Binary search the answer . For a fixed , don’t try to optimize anything — just ask: is there a path whose every produced component has weight at least ? Monotonicity is doing the heavy lifting here.
For an edge , define as the weight of the component containing after deleting edge . Then endpoint conditions on a chosen path are just and .
If a path passes through vertex using neighbors and , the component of after removing both path edges has weight
where . So the local compatibility condition is
Now the feasibility check becomes: find the longest path in the tree where endpoints satisfy , and every consecutive pair of edges through a vertex satisfies the compatibility inequality. If the longest such path has length at least , then a length exactly subpath also works, because removing fewer edges only merges positive-weight components at the ends.
Use reroot DP on directed edges. Let be the longest valid half-path ending with edge , with the condition at not checked yet. Then
At each vertex, sort neighbors by and use prefix top-two values to answer all transitions in linear time.
Let
If we can make every component have weight at least , then we can also do it for any smaller value. So the answer is found by binary search on .
Also, after removing exactly edges, there are components, hence
The real problem is the feasibility check for a fixed .
For an edge , define
These values are easy to compute from subtree sums after rooting the tree anywhere.
Consider a candidate path
For an endpoint, say , after deleting edge , its component weight is exactly
So endpoints require
For an internal vertex , with path-neighbors and , its component is everything except the two branches going through those two neighbors. Therefore its weight is
Thus the internal condition is
That is the key local condition. Once you see this, the tree stops looking scary and starts behaving.
For fixed , suppose we find a valid path of length . Then any contiguous subpath of length exactly 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 ?
Define as the maximum length of a valid half-path ending with directed edge .
More precisely, the path ends at , the previous vertex is , the far endpoint is already valid, and all internal vertices up to are already valid. Vertex is not checked yet.
There are two ways to form :
Start the path with just edge . Then is an endpoint, so we need
Extend some half-path ending at through a neighbor . Then becomes internal, so we need
Therefore
We use for impossible states.
A full valid path ending at through exists if additionally
and then its length is .
Root the tree at .
First compute all states from child to parent using a bottom-up pass. For , we only need incoming states from children of , which are already known.
Then compute states from parent to child using a top-down pass. When processing vertex , all incoming states from every neighbor are known, so we can compute outgoing states .
Classic reroot DP. Nothing fancy, just don’t trip over directions.
At a vertex , for every outgoing neighbor , we need
over neighbors satisfying
Sort neighbors of every vertex once by in descending order.
During one feasibility check, build prefix best and second-best values for each vertex. The second-best is needed to exclude without doing ugly hacks.
Since thresholds are monotonic while scanning sorted neighbors, all outgoing transitions of one vertex can be processed in
So one feasibility check costs
after the initial sorting.
The binary search gives total complexity
per test set, plus sorting adjacency lists once:
Memory is
#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;
}