ACM模板库

ACM模板库


模板

<pre><code class="language-cpp">//dsu on tree 大致框架 void dfs2(int u, int from, int opt){ int v; for (int i = head[u];~i;i=edge[i].nxt){ if ((v=edge[i].to)==from || v==son[u]) continue; dfs2(v, u, 0);//递归求解轻儿子答案 //删除轻儿子信息,也就对本树答案不做贡献 } //开始对本树答案进行计算 //重儿子信息保留,也就对本树答案有贡献 if (son[u]) dfs2(son[u], u, 1);//对重儿子进行求解 //对轻儿子信息进行暴力统计 calc(u, from, son[u]); //记录本树的答案 ans[u] = 统计后的信息; //如果,当前树不是父亲的重儿子的话,需要删除本树所有信息 if (!opt) del(u, from); } //重链剖分部分,处理重儿子 void dfs1(int u, int from){ sz[u] = 1;//以当前节点为根节点的树大小 int v; for (int i = head[u];~i;i=edge[i].nxt){ if ((v=edge[i].to)==from) continue; dfs1(v, u); //加上子树大小 sz[u] += sz[v]; //找到重儿子 if (sz[v]&gt;sz[son[u]]){ son[u] = v; } } } </code></pre>

页面列表

ITEM_HTML