校门外的枯树 Solution
y_kx_b
·
·
题解
呜呜，本来想友情在题面里提醒一下 B2（k=2 version）> C1 的，结果我不能修改团队题目/ng
\textbf{Sub }{\sf1}\textbf: 以根节点为一端点的链。
因为只有一个叶子节点，所以答案为 0 （因为所有边都在根到叶子节点的路径内，两个边集均为空）。
\textbf{Sub }{\sf6}\textbf: 链。
如果根节点不为链的端点，显然根节点答案为左右两条链的重量的最小值。非根节点转化为 \text{Sub }{\sf1}，答案为 0。
\textbf{Sub }{\sf5}\textbf: k=1 正解
一个简单 dfs 就结束了，这不需要讲吧（）。
好吧考虑到这题的位置还是讲讲吧，我们 dfs 这棵树，儿子就按照一个方向搜，当搜到叶子节点的时候统计这条链带来的贡献，最后所有贡献取最小值输出即可。
另外一个链式前向星的细节，读入顺序是从左往右，可前向星加边后遍历是反着的。这可能作为一个坑点，虽然这题没关系因为从左往右还是从右到左都一样。
代码中的 w1 代表链左边边集的边权和，w2 代表链上的边权和，(wsum - w2 - w1) 就是右边的边权和啦。
int wsum = 0/*读入完成后 wsum = 整棵树的边权总和*/, w1 = 0;
int ans = 0x7f7f7f7f;
void dfs(int u, int w2) {
if(head[u] == -1) {
ans = min(ans, abs((wsum - w2 - w1) - w1));
return;//其实这里写不写都无所谓，因为叶子节点肯定进不了下面这个循环（）
}
for(int i = head[u]; ~i; i = ne[i]) {
int &v = to[i];
dfs(v, w2 + w[i]);
w1 += w[i];
}
}
### $\textbf{Sub }{\sf4}\textbf:$ 菊花图。
容易发现问题可以转化为序列上的问题。
>有一个长度为 $n-1$ 的序列 $m$，计算 $\min\limits_{k=1}^{n-1}{\left\vert\sum\limits_{i=1}^{k-1}m_i-\sum\limits_{i=k+1}^{n-1}m_i\right\vert}$。
因为 $m_i>0$，所以这个柿子（绝对值内部）肯定是单调的。所以预处理后直接二分就行。
后来发现非根节点没有儿子，答案一定为 $0$，因此只需要计算根节点的答案，直接 $O(n)$ 枚举 $k$ 这个 Sub 就做完了，很遗憾没有太对正解起到启发作用/kk
### $\textbf{Sub }{\sf7}\textbf:$ $k=2$ 正解
~~其实就是上面这个 $\sout{O(\log n)\text{ Sub}{\sf4}}$。~~
我们发现，每当选择的叶子节点越来越靠右，右边的边权和减去左边的边权和一定越来越小（单调递减）。那么对于每个点的子树的询问，我们就可以直接二分，单次询问复杂度 $O(\log n)$。这里对于每个点都有询问，$q=n$，总复杂度为 $O(n\log n)$。
看个具体的例子吧。**注意这里我们假设 $2$ 为根。**
我们首先按照 $\text{Sub }{\sf5}$ 的 dfs 预处理出每个叶子节点**相对根的**的 `w1` 和 `w2` 以及每个点子树内包含的叶子节点的范围（即 dfs 序）。比如这里，`w1[9]=9+8+3+6+2+1`，`w1[3]=0`，`w2[7]=4+9+2`。那么我们就可以用前缀和思想，把相对于根节点的 `w` 变成相对于某个给出的根的 `w`，比如 $3$ 子树内的 $7$ 的 `w1` = `w1[7]-w1[3]=8+3+6`，`w2` 同理。
然后就可以二分啦。
std 写的很丑，仅供思路参考用 qwq
代码中 `ww1[i]` 表示节点 $i$ 的 `w1`，`w1[i]` 表示**第 $i$ 个叶子节点**的 `w1`；`w2`同理。`wsum` 为一个点子树内所有的边权总和。
```cpp
int k;
int to[N], ne[N], w[N], head[N], idx1 = 0;
void add(int u, int v, int W) {
to[idx1] = v, w[idx1] = W, ne[idx1] = head[u], head[u] = idx1++;
}
int wsum[N], ww1[N], ww2[N];
int w1[N], w2[N], idx2 = 0;
pii dfn[N];//左闭右开
int W1 = 0;
void dfs0(int u, int W2) {
dfn[u].x = idx2;
ww1[u] = W1, ww2[u] = W2;//ww1必须前序遍历记录。
if(head[u] == -1)
w1[/*u*/idx2] = W1, w2[idx2++] = W2;
for(int i = head[u]; ~i; i = ne[i]) {
int &v = to[i];
dfs0(v, W2 + w[i]);
wsum[u] += w[i] + wsum[v], W1 += w[i];
}
dfn[u].y = idx2;
}
int f(int u, int x) {
// ( wsum - w2 - w1 * 2);
return (wsum[u] - (w2[x] - ww2[u]) - (w1[x] - ww1[u]) * 2);
}
bool major(int T = 1) {
// memset(head, -1, sizeof head);// will TLE for T = 4e3
int n = read();
idx1 = idx2 = 0; W1 = 0;
for(int i = 1; i <= n; i++) head[i] = -1, wsum[i] = 0;
for(int i = 1; i <= n; i++) {
int q = read();
while(q--) {
int v = read(), y = read();
add(i, v, y);
}
}
dfs0(1, 0);
for(int u = 1; u <= n; u++) {
int l = dfn[u].x, r = dfn[u].y - 1;
while(l + 1 < r) {//五点七边二分法 yyds！
int mid = l + r >> 1;
if(f(u, mid) >= 0) l = mid; else r = mid;
}
// if(l == r) ans = abs(f(u, l)); else
// 本来要特判叶子节点，但是直接进入下面的语句也是对的（）。
int ans = min(abs(f(u, l)), abs(f(u, r)));
if(k == 2)
printf("%d%c", ans, " \n"[u == n]);
else //if(u == 1)
return printf("%d\n", ans);
}
return 0;
}
```
完结撒花！
彩蛋：题目中有一句白色的 $\sout{\text{不要问我为什么重量的字母是 }m\text。}$ ，不过好像梅友仁真正地问（）因为本来这场比赛就没给彩蛋供钱（
upd1 at 23.2.7：造数据时一直在想 $T$ 大了可能就放 $O(n^2)$ 过去了，结果忘了卡全局 `memset`（雾）。
upd2 at 23.4.28：唔，听说可以树形 dp？那是什么神仙做法，不懂。至少我尝试过然后没做出来/ng
upd3 at 24/12/06：原来之前一直把五点七边二分法（[二分查找为什么总是写错？](https://b23.tv/P0THoJu)）的 up 主记成了 3b1b，磕头谢罪）