自己做法,Wa了,求助!
查看原帖
自己做法,Wa了,求助!
878013
_Supernova楼主2023/11/21 22:27
#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e5 + 5;
int N, S, a, b, t, dp[maxN], dep_tree[maxN], dep_node[maxN], siz[maxN];
struct edge {
	int to, cost;
} h;
vector <edge> e[maxN];
void pre_dfs(int now, int f, int cos) {
	dep_node[now] = dep_node[f] + cos;
	if (e[now].size() == 1) {
		siz[now] = 1;
	}
	for (int i = 0; i < e[now].size(); ++i) {
		int v = e[now][i].to, w = e[now][i].cost;
		if (v == f) {
			continue;
		}
		pre_dfs(v, now, w);
		siz[now] += siz[v];
	}
	return ;
}
void dfs(int now, int f) {
	vector <int> son;
	for (int i = 0; i < e[now].size(); ++i) {
		int v = e[now][i].to, w = e[now][i].cost;
		if (v == f) {
			continue;
		}
		dep_tree[now] = max(dep_tree[now], w);
		dfs(v, now);
		dp[now] += dp[v];
		son.push_back(v); 
	}
	dep_tree[now] += dep_node[now];
	int max_w = -1;
	for (int i = 0; i < son.size(); ++i) {
		max_w = max(max_w, dep_tree[son[i]]);
	}
	for (int i = 0; i < son.size(); ++i) {
		dp[now] += (max_w - dep_tree[son[i]]) * siz[son[i]];
	}
	return ;
}
int main(void) {
	scanf("%d", &N);
	scanf("%d", &S);
	for (int i = 1; i < N; ++i) {
		scanf("%d %d %d", &a, &b, &t);
		h.to = b, h.cost = t;
		e[a].push_back(h);
		h.to = a;
		e[b].push_back(h);
	}
	pre_dfs(S, 0, 0);
	dfs(S, 0);
	printf("%d", dp[S]);
    return 0;
}
2023/11/21 22:27
加载中...