自动搬运

查看原文

来自洛谷，原作者为

	koukilee 如果...有一天你死了，我也不会忘记你的。除非...这个世界，不再下雨。

搬运于2025-08-24 23:10:05，当前版本为作者最后更新于2024-09-03 14:59:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

是啊，你是小怪兽，可小怪兽也有小怪兽的好朋友，孤独的小怪兽们害怕得靠在一起，但如果正义的奥特曼要来杀你，我就帮你把正义的奥特曼杀死。可是我答应了，却没有做到。

这里是出题人的题解。

题目大意

给定一颗 $n$ 个节点的树，边有边权 $w_i$。

每一个点往所有距离自己最远的点的简单路径上的点的权值加 $1$。

求最后所有点的点权和。

$1\le n\le10^6,0\le w_i\le10^9$。

题目解析

对于前 $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$。

使用了换根的做法，以下皆用样例一作为解释。

如下图：

此时我们钦定红点 $1$ 为根，每条边的边权为这个点到 $1$ 节点的距离。

明显对最终答案的贡献是 $8$，最远距离是 $3$。

此时我们将根转移到 $2$ 上，答案变成了 $6$，最远距离为 $2$。

我们可以总结出一个规律：当一个点 $u$ 换根到他的子节点 $v$ 时，只需要将在 $u$ 子树内的节点到 $u$ 的距离全部减去 $w_{u, v}$，非子树以外的节点全部加上 $w_{u, v}$，即可实现边权的动态变化。

这里暴力实现还是 $O(n)$ 的，我们可以使用线段树维护 dfs 序，同时可以 $O(\log n)$ 修改和查询。

---

紧接着思考怎么用线段树来合并答案。

我们线段树维护了 $3$ 个值 $count,dis,res$。

$dis$ 表示当前节点到根节点的最大深度。

$count$ 表示当前为最大深度 $dis$ 的情况下，一共有多少条不同的路径。

$res$ 用于存储答案。

---

push_up 我们需要分类讨论：

当 $ls$ 和 $rs$ 的 $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;

否则就直接继承 $dis$ 最大的那个儿子：

if (tree[k << 1].dis > tree[k << 1 | 1].dis)
		tree[k] = tree[k << 1];
else tree[k] = tree[k << 1 | 1];

同时需要区间修改，再维护一个 lazy tag 即可。

---

到此为止这道题已经差不多了，但是还有点小细节：

注意这个换根的转移顺序，必须从自己的父亲节点转移过来，意味着我们以 dfs 的顺序换根，回溯的时候不能忘记对线段树进行回溯。

题解里使用的是手写的树遍历（需要使用当前弧优化，也就是模拟 dfs），为的是减少 dfs 的栈空间和常数，本题轻微卡常。

否则只能拿到 对于 $40\%$ 的数据： $n\le 5\times 10^{5},w_i\le 10^9$。

时间复杂度：$O(n \log n)$。

另有 $O(n)$ 的 DP 做法，在此不再阐述。

STD

/* 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;
		}
	}
}

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;
	
	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;
}