「KFCOI Round #1」遥不可及题解
koukilee
·
·
题解
UPD（2025.11.9）：鉴于本题为出题人低年级时所想，可能题目质量和题解做法都有所欠缺。同时更新文章的 MD。
如果正义的奥特曼要来杀你，我就帮你把正义的奥特曼杀死。可是我答应了，却没有做到。
题目大意
给定一颗 n 个节点的树，边有边权 w_i。
每一个点往所有距离自己最远的点的简单路径上的点的权值加 1。
求最终所有点的点权和。
题目解析
:::info[部分分]
- 对于前 30\% 的数据，满足 1\le n \le 5000：
注意数据范围较小，于是对于每个点跑一次搜索，找到最远的点，给对应路径上的权值加 1 即可。
注意开 long long。
时间复杂度：O(n^2)。
- 对于另外 10\% 的数据，满足 n\le 10^6，且树的形态为一条链：
如果是一条链的情况，先遍历遍这条链，做一个前缀的长度和。
对于每一个点，明显一定会取到链的两头长度才能达到最长，我们比较这个点到两头的长度即可。
注意可能两头长度一样。
时间复杂度：O(n)，Code。
- 对于另外 10\% 的数据，满足 n\le 5\times 10^5，且树的形态为菊花：
求出中心点距离其他点的最大值和次大值，及其数量。
对于菊花中心点，明显是选择最大值，加上最大值数量 \times 2 即可。
对于周围的点，它到中心点的距离是确定的，那么我们就是选择除了此点以外距离最远的点。
如果中心点到此点就是最大值，并且最大值只有一个，那么加上 次大值的数量 \times 3 。否则加上 (最大值数量 - 1) \times 3 即可。此处 \times 3 的原因是，从当前点走到中心点每次都还有 2 的贡献。
如果中心点到此点不是最大值，直接加上 最大值数量 \times 3 即可。
时间复杂度：O(n)，Code。
:::
- 对于 100\% 的数据，满足 1\le n\le 10^6，0\le w_i \le 10^9：
出题的时候水平比较低，使用了换根的做法。
:::info[思路]
以下皆用样例一作为解释。如下图：
此时我们钦定红点 1 为根，每条边的边权为这个点到 1 节点的距离。
明显对最终答案的贡献是 8，最远距离是 3。
此时我们将根转移到 2 上，答案变成了 6，最远距离为 2。
我们可以总结出一个规律：当一个点 u 换根到他的子节点 v 时，只需要将在 u 子树内的节点到 u 的距离全部减去 w_{u, v}，非子树以外的节点全部加上 w_{u, v}，即可实现边权的动态变化。
这是非常经典的换根。
暴力实现可以做到 O(n)，但是我们可以使用线段树维护 dfs 序，同时 O(\log n) 修改和查询。
:::
合并答案是简单的。
我们线段树维护了 3 个值 dis，count，res，分别表示：当前节点到根节点的最大深度；当前为最大深度 dis 的情况下，一共有多少条不同的路径；用于存储答案。
上传信息时我们需要分类讨论：
当左右子树的 dis 相同时，总路径数要合并到一起，答案相加。否则就直接继承 dis 最大的那个儿子。
区间修改只需要再维护一个懒标记即可。
本题轻微卡常，需要注意一下实现，否则只能拿到对于 40\% 的数据：
时间复杂度：$O(n \log n)$，另有 $O(n)$ 的 DP 和更简单的树的直径的做法，在此不再阐述。
:::success[Code]
```c++
/* The code is from koukilee*/
struct edge{i32 u, v, d, nex;}g[MAXN << 1];
struct Tree{i32 count; i64 dis, res;}tree[MAXN << 2];
i32 n, first[MAXN], cnt, dfn[MAXN], id, size[MAXN], fdep[MAXN], dfa[MAXN], rev[MAXN], cur[MAXN], stack[MAXN], sta;
i64 ans, fw[MAXN], lazy[MAXN << 2], tazy[MAXN << 2];
bool vis[MAXN];
inline void update(i32 u, i32 v, i32 d) noexcept{g[++cnt] = (edge){u, v, d, first[u]}, first[u] = cnt;}
void dfs (i32 u, i32 fa) noexcept{
dfn[u] = ++id, rev[id] = u, size[u] = 1;
for (i32 i = first[u]; i; i = g[i].nex){
if (g[i].v != fa){
fdep[g[i].v] = fdep[u] + 1, fw[g[i].v] = fw[u] + g[i].d;
dfs(g[i].v, u), size[u] += size[g[i].v];
dfa[g[i].v] = g[i].d;
}
}
} /*dfs 序以及一些预处理*/
inline void push_up (i32 k) noexcept{
if (tree[k << 1].dis == tree[k << 1 | 1].dis){
tree[k].count = tree[k << 1].count + tree[k << 1 | 1].count, tree[k].res = tree[k << 1].res + tree[k << 1 | 1].res;
tree[k].dis = tree[k << 1].dis;
}
else if (tree[k << 1].dis > tree[k << 1 | 1].dis)
tree[k] = tree[k << 1];
else tree[k] = tree[k << 1 | 1];
} /*合并信息和分类讨论*/
inline void push_down (i32 k) noexcept{
tree[k << 1].res += tree[k << 1].count * tazy[k], tree[k << 1].dis += lazy[k];
tree[k << 1 | 1].res += tree[k << 1 | 1].count * tazy[k], tree[k << 1 | 1].dis += lazy[k];
lazy[k << 1] += lazy[k], lazy[k << 1 | 1] += lazy[k];
tazy[k << 1] += tazy[k], tazy[k << 1 | 1] += tazy[k];
lazy[k] = tazy[k] = 0;
} /*下传标记*/
void build (i32 k, i32 l, i32 r) noexcept{
if (l == r){
tree[k].count = 1, tree[k].res = fdep[rev[l]], tree[k].dis = fw[rev[l]];
return;
}
i32 mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
push_up(k);
}
void change (i32 k, i32 l, i32 r, i32 x, i32 y, i32 v, i32 cw) noexcept{
if (x <= l && r <= y){
tree[k].res += tree[k].count * v, tree[k].dis += v * cw;
lazy[k] += v * cw, tazy[k] += v ;
return;
}
i32 mid = (l + r) >> 1; push_down(k);
if (x <= mid) change(k << 1, l, mid, x, y, v, cw);
if (y > mid) change(k << 1 | 1, mid + 1, r, x, y, v, cw);
push_up(k);
}
int main() noexcept{
read(n);
for (i32 i = 1, x, y, d; i < n; i++){
read(x, y, d); update(x, y, d), update(y, x, d);
}
for (i32 i = 1; i <= n; i++)
cur[i] = first[i];
fdep[1] = 1;
dfs(1, 0);
build(1, 1, n);
stack[++sta] = 1, ans += tree[1].res, vis[1] = 1;
/*为了卡常模拟了递归 dfs*/
while (sta > 0){
i32 nex = stack[sta], f = 0;
for (i32 i = cur[nex]; i; i = g[i].nex){
cur[nex] = i;
if (g[i].v != nex && !vis[g[i].v]){
stack[++sta] = g[i].v, f = 1, vis[g[i].v] = 1;
change(1, 1, n, 1, n, 1, dfa[g[i].v]), change(1, 1, n, dfn[g[i].v], dfn[g[i].v] + size[g[i].v] - 1, -2, dfa[g[i].v]);
ans += tree[1].res;
break;
}
}
if (!f)
change(1, 1, n, 1, n, -1, dfa[nex]), change(1, 1, n, dfn[nex], dfn[nex] + size[nex] - 1, 2, dfa[nex]), sta--; /*换根，注意要删除*/
}
put(ans);
return 0;
}
```
:::