python-tree-multicut-terminal-isolation-dp
I diagnosed the tree multiway cut problem and produced a verified O(N) bottom-up 0/1 DP solution.
Root cause of naive approaches failing: per-terminal min-cut is O(K·N) and an O(N·K) state DP is unusable at N,K ≤ 2·10⁵. The key insight is that we only need to know whether a component contains a terminal (at most one per final component), not which terminal — collapsing the DP to two values per node.
The fix: For each node v, compute two values tracked from its subtree:
- dp0[v]: min cut cost with the component containing v holding no terminal
- dp1[v]: min cut cost with it holding exactly one terminal
For each child edge (v,c,w), either cut (pay w, child's status is free) or keep (statuses OR together, but a component may hold ≤1 terminal — so acc1+c1 is excluded). Answer = min(dp0[root], dp1[root]).
Verification performed:
- 3,000 random trees + 2,400 structured trees (paths/stars/caterpillars) cross-checked against exhaustive 2^(N-1) subset brute force (DSU component check) — all passed
- Edge cases: zero/one terminal → 0; all-marked chain → all edges; star case confirmed vs brute force
- 64-bit correctness: worst-case answer 199999000000000 > 2^31-1, computed exactly
- Performance at N=K=2·10⁵: ~0.45s (well under limits)
All artifacts are in ~/tree_multicut/:
- solution.py — the verified DP
- brute.py, test_random.py, test_structured.py, test_edge.py — verification suite
- SOLUTION.md — self-contained root-cause analysis, the exact fix, and full verification section
# Evidence - Problem class: python-tree-multicut-terminal-isolation-dp - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-20T04:11:43.439Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a connected weighted tree with N up to 2e5 nodes and K up to 2e5 marked terminals, find the minimum total weight of edges to delete so that every pair of marked nodes lands in different connected components (tree multiway cut). Derive a bottom-up DP with a 0/1 state per node (does the component attached to the node still contain a terminal), where keeping a child edge forces the child into the 0-state and cutting it costs the edge weight; naive per-terminal min-cut or O(N*K) approaches must be beaten. Edge weights are up to 1e9 and the answer can exceed 32 bits, so print the minimum cost as a 64-bit integer.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-tree-multicut-terminal-isolation-dp", "provider": "openrouter", "solved_at": "2026-08-20T04:11:43.439Z", "version": "3.11"}I diagnosed the tree multiway cut problem and produced a verified O(N) bottom-up 0/1 DP solution.
Root cause of naive approaches failing: per-terminal min-cut is O(K·N) and an O(N·K) state DP is unusable at N,K ≤ 2·10⁵. The key insight is that we only need to know whether a component contains a terminal (at most one per final component), not which terminal — collapsing the DP to two values per node.
The fix: For each node v, compute two values tracked from its subtree:
- dp0[v]: min cut cost with the component containing v holding no terminal
- dp1[v]: min cut cost with it holding exactly one terminal
For each child edge (v,c,w), either cut (pay w, child's status is free) or keep (statuses OR together, but a component may hold ≤1 terminal — so acc1+c1 is excluded). Answer = min(dp0[root], dp1[root]).
Verification performed:
- 3,000 random trees + 2,400 structured trees (paths/stars/caterpillars) cross-checked against exhaustive 2^(N-1) subset brute force (DSU component check) — all passed
- Edge cases: zero/one terminal → 0; all-marked chain → all edges; star case confirmed vs brute force
- 64-bit correctness: worst-case answer 199999000000000 > 2^31-1, computed exactly
- Performance at N=K=2·10⁵: ~0.45s (well under limits)
All artifacts are in ~/tree_multicut/:
- solution.py — the verified DP
- brute.py, test_random.py, test_structured.py, test_edge.py — verification suite
- SOLUTION.md — self-contained root-cause analysis, the exact fix, and full verification section
# Evidence - Problem class: python-tree-multicut-terminal-isolation-dp - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-20T04:11:43.439Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a connected weighted tree with N up to 2e5 nodes and K up to 2e5 marked terminals, find the minimum total weight of edges to delete so that every pair of marked nodes lands in different connected components (tree multiway cut). Derive a bottom-up DP with a 0/1 state per node (does the component attached to the node still contain a terminal), where keeping a child edge forces the child into the 0-state and cutting it costs the edge weight; naive per-terminal min-cut or O(N*K) approaches must be beaten. Edge weights are up to 1e9 and the answer can exceed 32 bits, so print the minimum cost as a 64-bit integer.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-tree-multicut-terminal-isolation-dp", "provider": "openrouter", "solved_at": "2026-08-20T04:11:43.439Z", "version": "3.11"}