Submission #2301296

---

Source Code Expand

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
struct edge {
	int to, cost;
	edge() : to(-1), cost(0) {};
	edge(int to_, int cost_) : to(to_), cost(cost_) {};
};
int X;
long long calc(vector<int> v) {
	int N = v.size();
	sort(v.begin(), v.end());
	long long ret = 0, sum = 0; int pl = 0;
	for (int i = N - 1; i >= 0; i--) {
		while (pl != N && v[i] + v[pl] < X) sum += v[pl++];
		ret += sum + 1LL * pl * v[i] + 1LL * (N - pl) * X;
		ret -= min(v[i] * 2, X);
	}
	return ret / 2;
}
long long solve(vector<vector<edge> > G) {
	int N = G.size();
	if (N == 1) return 0;
	vector<int> c(N);
	function<void(int, int)> init_dfs = [&](int pos, int pre) {
		c[pos] = 1;
		for (edge e : G[pos]) {
			if (e.to == pre) continue;
			init_dfs(e.to, pos);
			c[pos] += c[e.to];
		}
	};
	init_dfs(0, -1);
	int gravity = -1;
	for (int i = 0; i < N; i++) {
		bool ok = (c[i] * 2 >= N);
		for (edge e : G[i]) {
			if (c[e.to] < c[i] && c[e.to] * 2 > N) ok = false;
		}
		if (ok) gravity = i;
	}
	long long ret = 0;
	vector<int> all_d({ 0 });
	for (edge e : G[gravity]) {
		vector<vector<edge> > GN(1);
		vector<int> d({ min(e.cost, X + 1) });
		function<void(int, int, int)> dfs = [&](int pos, int id, int pre) {
			for (edge ee : G[pos]) {
				if (ee.to == pre) continue;
				GN[id].push_back(edge(GN.size(), ee.cost));
				GN.push_back({ edge(id, ee.cost) });
				d.push_back(min(d[id] + ee.cost, X + 1));
				dfs(ee.to, GN.size() - 1, pos);
			}
		};
		dfs(e.to, 0, gravity);
		all_d.insert(all_d.end(), d.begin(), d.end());
		ret -= calc(d);
		ret += solve(GN);
	}
	ret += calc(all_d);
	return ret;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N >> X;
	vector<int> A(N - 1), B(N - 1), C(N - 1), D(N, 1 << 30);
	vector<vector<edge> > G(N);
	for (int i = 0; i < N - 1; i++) {
		cin >> A[i] >> B[i] >> C[i], A[i]--, B[i]--;
		G[A[i]].push_back(edge(B[i], C[i])); D[A[i]] = min(D[A[i]], C[i]);
		G[B[i]].push_back(edge(A[i], C[i])); D[B[i]] = min(D[B[i]], C[i]);
	}
	long long ret = solve(G);
	for (int i = 0; i < N - 1; i++) {
		ret -= min(C[i], X);
		int val = min(C[i], X + min(D[A[i]], D[B[i]]));
		if (G[A[i]].size() + G[B[i]].size() != N) val = min(val, 2 * X);
		else if (G[A[i]].size() != 1 && G[B[i]].size() != 1) val = min(val, 3 * X);
		ret += val;
	}
	cout << ret << endl;
	return 0;
}

Submission Info

Judge Result