Roads in Hacker Land - C++ 14 - study the code -

RoadsInHackerLand2A.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
pair<int, pair<int, int> >a[200020];
vector<pair<int, int> >e[100020];
int n, m;
int f[100020];
int s[100020];
long long ans[400020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}

void dfs(int x, int y) {
	s[x] = 1;
	for (int i = 0; i < e[x].size(); i++) {
		if (e[x][i].first == y) {
			continue;
		}
		dfs(e[x][i].first, x);
		s[x] += s[e[x][i].first];
		ans[e[x][i].second] += (long long)(n - s[e[x][i].first]) * s[e[x][i].first];
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first);
	}
	sort(a, a + m);
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		if (F(a[i].second.first) == F(a[i].second.second)) {
			continue;
		}
		int x = a[i].second.first;
		int y = a[i].second.second;
		int v = a[i].first;
		int fx = F(x);
		int fy = F(y);
		f[fy] = fx;
		e[x].push_back(make_pair(y, v));
		e[y].push_back(make_pair(x, v));
	}
	dfs(1, 0);
	for (int i = 0; i < 2 * m + 10; i++) {
		ans[i + 1] += ans[i] / 2;
		ans[i] %= 2;
	}
	int gqy = 2 * m + 10;
	while (ans[gqy - 1] == 0) {
		gqy--;
	}
	for (int i = gqy - 1; i >= 0; i--) {
		printf("%lld", ans[i]);
	}
	printf("\n");
	return 0;
}