Knapsack-style DP assumed an array order. On a tree the 'prefix' is a subtree. Classic: size[v] = 1 + Σ size[child]. Classic hard: CSES Tree Matching — take a matching edge to one child or not; CSES Tree Distances II — sum of distances from every node (compute down, then reroot up).
USACO Gold 'DP on Trees'. The WA is treating the tree as a DAG without rooting it, or double-counting the parent as a child.
function subtreeSizes(n, edges, root = 0) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const size = Array(n).fill(1);
function dfs(v, p) {
for (const u of adj[v]) {
if (u === p) continue;
dfs(u, v);
size[v] += size[u];
}
}
dfs(root, -1);
return size;
}Checks 0/2