{"id":"dsa/small-to-large#order-6gxuff","promptHtml":"Arrange the body of dfs(v, p, keep) for DSU on tree.","lang":"cpp","lines":[{"text":"for (int u : g[v]) if (u != p && u != heavy[v]) dfs(u, v, false);","html":"for (int u : g[v]) if (u != p && u != heavy[v]) dfs(u, v, false);"},{"text":"if (heavy[v] != -1) dfs(heavy[v], v, true);","html":"if (heavy[v] != -1) dfs(heavy[v], v, true);"},{"text":"addVertex(v);","html":"addVertex(v);"},{"text":"for (int u : g[v]) if (u != p && u != heavy[v])","html":"for (int u : g[v]) if (u != p && u != heavy[v])"},{"text":" for (int t = tin[u]; t < tout[u]; t++) addVertex(ver[t]);","html":" for (int t = tin[u]; t < tout[u]; t++) addVertex(ver[t]);"},{"text":"ans[v] = sumDom;","html":"ans[v] = sumDom;"},{"text":"if (!keep) { for (int t = tin[v]; t < tout[v]; t++) cntc[c[ver[t]]]--; mx = 0; sumDom = 0; }","html":"if (!keep) { for (int t = tin[v]; t < tout[v]; t++) cntc[c[ver[t]]]--; mx = 0; sumDom = 0; }"}],"distractors":[{"text":" if (keep) { for (int t = tin[v]; t < tout[v]; t++) cntc[c[ver[t]]]--; }","html":" if (keep) { for (int t = tin[v]; t < tout[v]; t++) cntc[c[ver[t]]]--; }"}],"whyHtml":"Light children go first so their data is cleared, then the heavy child is processed last and kept. Only after both is the subtree of v assembled. Clearing must happen when keep is false, otherwise a light subtree would pollute its parent's counters."}