虚树

这题真的是写到心态爆炸。。 一道边分治 + 虚树 前置知识边分治顾名思义，就是选择一条边，类似点分治对所有经过该边的路径进行处理，但与点分治不同的是，边分治可能会被菊花图卡到 $O (n^2)$，故此时需要重构树，将之变为度数不超过三的二叉树 树重构通过建立新的虚点进行重构，但要满足加入的虚点不影响最后答案计算 12345678910111213141516171819void rebuild (int root, int father) { int nf = 0; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; LL w = Link[i].w; if (v == father) continue; if (! nf) { Insert (root, v, w), Insert (v, root, w); nf = root; } else { int k = ++ m; // 虚点 Insert (nf, k, 0), ...