Submission #2242436

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

struct Edge {
	int dest, weight;
	Edge() {}
	Edge(int _dest, int _weight) : dest(_dest), weight(_weight) {}
};
vector<Edge> edges[N];
long long dist[N];
int n, size[N], mx[N];

void dfs(int x, int pre) {
	size[x] = 1;
	for (int i = 0; i < edges[x].size(); ++i) {
		int y = edges[x][i].dest, w = edges[x][i].weight;
		if (y != pre) {
			dist[y] = w;
			dfs(y, x);
			size[x] += size[y];
			mx[x] = max(mx[x], size[y]);
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		edges[x].push_back(Edge(y, w));
		edges[y].push_back(Edge(x, w));
	}
	dfs(1, 0);
	long long ans = 0LL;
	for (int i = 1; i <= n; ++i) {
		ans += min(size[i], n - size[i]) * dist[i];
		mx[i] = max(mx[i], n - size[i]);
	}
	ans <<= 1;
	vector<int> root;
	root.push_back(1);
	for (int i = 2; i <= n; ++i)
		if (mx[i] < mx[root[0]]) {
			root.clear();
			root.push_back(i);
		} else if (mx[i] == mx[root[0]])
			root.push_back(i);
	assert(root.size() <= 2);
	if (root.size() == 2) {
		int x = root[0];
		for (int i = 0; i < edges[x].size(); ++i) {
			int y = edges[x][i].dest, w = edges[x][i].weight;
			if (y == root[1]) ans -= w;
		}
	} else {
		int x = root[0], min_weight = INT_MAX;
		for (int i = 0; i < edges[x].size(); ++i)
			min_weight = min(min_weight, edges[x][i].weight);
		ans -= min_weight;
	}
	printf("%lld\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:32:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &w);
                              ^

Judge Result