luoguP1131 时态同步

有N个节点构成的电路树，编号为S的的节点为激发器，会产生电流并通过导线往下传递，给出电流在各边上传递递需要的时间w[i][j]，可以花1个单位的代价将任意1条边的耗时加1，现要求电流同时到达所有叶子节点，求修改边的最小代价。
1<=N<=5E5; 1<=w[i][j]<=1E6

分析：自下而上dp，对于节点x，先算出以x为根的子树，x到叶子的最大距离，然后再次遍历所有子节点计算差值并累加。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
	int N, S;
	std::cin >> N >> S;
	S--;
	std::vector<std::vector<std::pair<int,int>>> adj(N);
	for (int i = 1; i < N; i++) {
		int x, y, z;
		std::cin >> x >> y >> z;
		x--, y--;
		adj[x].push_back({y, z});
		adj[y].push_back({x, z});
	}

	i64 ans = 0;
	std::vector<i64> dis(N);

	auto dfs = [&](auto self, int x, int p) -> void {
		for (auto &pr : adj[x]) if (pr.first != p) {
			self(self, pr.first, x);
			dis[x] = std::max(dis[x], dis[pr.first] + pr.second);
		}
		for (auto &pr : adj[x]) if (pr.first != p) {
			ans += dis[x] - dis[pr.first] - pr.second;
		}
	};

	dfs(dfs, S, S);
	std::cout << ans << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}