Submission #3316382

---

Source Code Expand

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

#define sz(x) (int)x.size() 
#define pb push_back 
#define mp make_pair 
#define fi(a, b) for(int i=a; i<=b; i++) 
#define fj(a, b) for(int j=a; j<=b; j++) 
#define fo(a, b) for(int o=a; o<=b; o++) 
#define fdi(a, b) for(int i=a; i>=b; i--) 
#define fdj(a, b) for(int j=a; j>=b; j--) 
#define fdo(a, b) for(int o=a; o>=b; o--) 

#ifdef LOCAL
#define err(...) fprintf(stderr, __VA_ARGS__)
#else
#define err(...) while(false) {}
#endif

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<int> vi; 
typedef vector<ll> vll;
typedef vector<pii> vpii; 
typedef vector<pll> vpll; 
typedef long double ld;
typedef unsigned long long ull;

/////////////////////////////////

int const MAX = 1e5 + 41;

int n;
int a[MAX];
int b[MAX];
int c[MAX];

vi per;

bool cmp(int i, int j) {
	return c[i] > c[j];
}

int par[MAX];
ll ans[MAX];
ll add[MAX];
vi ver[MAX];

int find(int x) {
	if (par[x] == x) return x;
	return par[x] = find(par[x]);
}

void solve() {
	fi(1, n - 1) {
		per.pb(i);
	}
	sort(per.begin(), per.end(), cmp);

	fi(1, n) {
		par[i] = i;
		ver[i].pb(i);
	}

	for (int id : per) {
		int x = find(a[id]);
		int y = find(b[id]);
		if (sz(ver[x]) < sz(ver[y])) {
			swap(x, y);
		}
		for (int z : ver[y]) {
			ans[z] += add[y];
			ans[z] += (ll) (sz(ver[x]) - sz(ver[y])) * c[id];
			ans[z] -= add[x];
		}
		add[y] = 0;
		add[x] += (ll) sz(ver[y]) * c[id];
		ver[x].insert(ver[x].end(), ver[y].begin(), ver[y].end());
		par[y] = x;
	}
	fi(1, n) {
		ans[i] += add[find(i)];
		printf("%lld\n", ans[i]);
	}
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

  scanf("%d", &n);
  fi(1, n - 1) {
  	scanf("%d %d %d", &a[i], &b[i], &c[i]);
  }
	solve();		

	
#ifdef LOCAL
	err("ELAPSED TIME: %.3Lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:96:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &a[i], &b[i], &c[i]);
                                          ^

Judge Result