Language: C++

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;

template<typename T>
void read(T &x) {
	int flag = 1; x = 0; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}

const int N = 1e6 + 10;
int n, w[N], Size, MX, rt, siz[N], fa[N];
int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
bool vis[N];
inline void addEdge(int u, int v, int w) {
	to[++cnt] = v, dis[cnt] = w, nxt[cnt] = from[u], from[u] = cnt;
}
struct Edge { int u, v; ll w; } e[N]; int m;
inline bool operator < (const Edge &a, const Edge &b) { return a.w < b.w; }

void getrt(int u, int fa) {
	int maxpart = 0; siz[u] = 1;
	for(int i = from[u]; i; i = nxt[i]) {
		int v = to[i]; if(vis[v] || v == fa) continue;
		getrt(v, u), siz[u] += siz[v];
		maxpart = max(maxpart, siz[v]);
	} maxpart = max(maxpart, Size - siz[u]);
	if(maxpart < MX) MX = maxpart, rt = u;
}
int P; ll val, ans;

void dfs(int u, int fa, ll dep) {
	if(dep + w[u] < val) val = dep + w[u], P = u;
	for(int i = from[u]; i; i = nxt[i])
		if(!vis[to[i]] && to[i] != fa)
			dfs(to[i], u, dep + dis[i]);
}

void Link(int u, int fa, ll dep) {
	e[++m] = (Edge){u, P, val + dep + w[u]};
	for(int i = from[u]; i; i = nxt[i])
		if(!vis[to[i]] && to[i] != fa)
			Link(to[i], u, dep + dis[i]);
}

void doit(int u) {
	vis[u] = 1, val = 1e18, P = 0;
	dfs(u, 0, 0), Link(u, 0, 0);
	for(int i = from[u]; i; i = nxt[i]) {
		int v = to[i]; if(vis[v]) continue;
		Size = MX = siz[v], getrt(v, u), doit(rt);
	}
}

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main () {
#ifdef OFFLINE_JUDGE
	freopen("233.in", "r", stdin);
	freopen("233.out", "w", stdout);
#endif
	read(n);
	for(int i = 1; i <= n; ++i) read(w[i]);
	for(int i = 1, u, v, w; i < n; ++i) {
		read(u), read(v), read(w);
		addEdge(u, v, w), addEdge(v, u, w);
	}
	Size = MX = n; getrt(1, 0), doit(rt);
	sort(e + 1, e + m + 1); int blo = n;
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 1; i <= m && blo > 1; ++i) {
		int u = find(e[i].u), v = find(e[i].v);
		if(u != v) ans += e[i].w, fa[u] = v, --blo;
	} printf("%lld\n", ans);
	return 0;
} 
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;

template<typename T>
void read(T &x) {
	int flag = 1; x = 0; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}

const int N = 1e6 + 10;
int n, w[N], Size, MX, rt, siz[N], fa[N];
int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
bool vis[N];
inline void addEdge(int u, int v, int w) {
	to[++cnt] = v, dis[cnt] = w, nxt[cnt] = from[u], from[u] = cnt;
}
struct Edge { int u, v; ll w; } e[N]; int m;
inline bool operator < (const Edge &a, const Edge &b) { return a.w < b.w; }

void getrt(int u, int fa) {
	int maxpart = 0; siz[u] = 1;
	for(int i = from[u]; i; i = nxt[i]) {
		int v = to[i]; if(vis[v] || v == fa) continue;
		getrt(v, u), siz[u] += siz[v];
		maxpart = max(maxpart, siz[v]);
	} maxpart = max(maxpart, Size - siz[u]);
	if(maxpart < MX) MX = maxpart, rt = u;
}
int P; ll val, ans;

void dfs(int u, int fa, ll dep) {
	if(dep + w[u] < val) val = dep + w[u], P = u;
	for(int i = from[u]; i; i = nxt[i])
		if(!vis[to[i]] && to[i] != fa)
			dfs(to[i], u, dep + dis[i]);
}

void Link(int u, int fa, ll dep) {
	e[++m] = (Edge){u, P, val + dep + w[u]};
	for(int i = from[u]; i; i = nxt[i])
		if(!vis[to[i]] && to[i] != fa)
			Link(to[i], u, dep + dis[i]);
}

void doit(int u) {
	vis[u] = 1, val = 1e18, P = 0;
	dfs(u, 0, 0), Link(u, 0, 0);
	for(int i = from[u]; i; i = nxt[i]) {
		int v = to[i]; if(vis[v]) continue;
		Size = MX = siz[v], getrt(v, u), doit(rt);
	}
}

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main () {
#ifdef OFFLINE_JUDGE
	freopen("233.in", "r", stdin);
	freopen("233.out", "w", stdout);
#endif
	read(n);
	for(int i = 1; i <= n; ++i) read(w[i]);
	for(int i = 1, u, v, w; i < n; ++i) {
		read(u), read(v), read(w);
		addEdge(u, v, w), addEdge(v, u, w);
	}
	Size = MX = n; getrt(1, 0), doit(rt);
	sort(e + 1, e + m + 1); int blo = n;
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 1; i <= m && blo > 1; ++i) {
		int u = find(e[i].u), v = find(e[i].v);
		if(u != v) ans += e[i].w, fa[u] = v, --blo;
	} printf("%lld\n", ans);
	return 0;
} 


Compiler output:
a.cc:90:6: error: redefinition of 'template<class T> void read(T&)'
   90 | void read(T &x) {
      |      ^~~~
a.cc:10:6: note: 'template<class T> void read(T&)' previously declared here
   10 | void read(T &x) {
      |      ^~~~
a.cc:96:11: error: redefinition of 'const int N'
   96 | const int N = 1e6 + 10;
      |           ^
a.cc:16:11: note: 'const int N' previously defined here
   16 | const int N = 1e6 + 10;
      |           ^
a.cc:97:5: error: redefinition of 'int n'
   97 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |     ^
a.cc:17:5: note: 'int n' previously declared here
   17 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |     ^
a.cc:97:8: error: redefinition of 'int w [1000010]'
   97 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |        ^
a.cc:17:8: note: 'int w [1000010]' previously declared here
   17 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |        ^
a.cc:97:14: error: redefinition of 'int Size'
   97 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |              ^~~~
a.cc:17:14: note: 'int Size' previously declared here
   17 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |              ^~~~
a.cc:97:20: error: redefinition of 'int MX'
   97 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                    ^~
a.cc:17:20: note: 'int MX' previously declared here
   17 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                    ^~
a.cc:97:24: error: redefinition of 'int rt'
   97 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                        ^~
a.cc:17:24: note: 'int rt' previously declared here
   17 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                        ^~
a.cc:97:28: error: redefinition of 'int siz [1000010]'
   97 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                            ^~~
a.cc:17:28: note: 'int siz [1000010]' previously declared here
   17 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                            ^~~
a.cc:97:36: error: redefinition of 'int fa [1000010]'
   97 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                                    ^~
a.cc:17:36: note: 'int fa [1000010]' previously declared here
   17 | int n, w[N], Size, MX, rt, siz[N], fa[N];
      |                                    ^~
a.cc:98:5: error: redefinition of 'int cnt'
   98 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |     ^~~
a.cc:18:5: note: 'int cnt' previously declared here
   18 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |     ^~~
a.cc:98:10: error: redefinition of 'int from [1000010]'
   98 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |          ^~~~
a.cc:18:10: note: 'int from [1000010]' previously declared here
   18 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |          ^~~~
a.cc:98:19: error: redefinition of 'int to [2000020]'
   98 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |                   ^~
a.cc:18:19: note: 'int to [2000020]' previously declared here
   18 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |                   ^~
a.cc:98:31: error: redefinition of 'int dis [2000020]'
   98 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |                               ^~~
a.cc:18:31: note: 'int dis [2000020]' previously declared here
   18 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |                               ^~~
a.cc:98:44: error: redefinition of 'int nxt [2000020]'
   98 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |                                            ^~~
a.cc:18:44: note: 'int nxt [2000020]' previously declared here
   18 | int cnt, from[N], to[N << 1], dis[N << 1], nxt[N << 1];
      |                                            ^~~
a.cc:99:6: error: redefinition of 'bool vis [1000010]'
   99 | bool vis[N];
      |      ^~~
a.cc:19:6: note: 'bool vis [1000010]' previously declared here
   19 | bool vis[N];
      |      ^~~
a.cc:100:13: error: redefinition of 'void addEdge(int, int, int)'
  100 | inline void addEdge(int u, int v, int w) {
      |             ^~~~~~~
a.cc:20:13: note: 'void addEdge(int, int, int)' previously defined here
   20 | inline void addEdge(int u, int v, int w) {
      |             ^~~~~~~
a.cc:103:8: error: redefinition of 'struct Edge'
  103 | struct Edge { int u, v; ll w; } e[N]; int m;
      |        ^~~~
a.cc:23:8: note: previous definition of 'struct Edge'
   23 | struct Edge { int u, v; ll w; } e[N]; int m;
      |        ^~~~
a.cc:103:33: error: conflicting declaration 'int e [1000010]'
  103 | struct Edge { int u, v; ll w; } e[N]; int m;
      |                                 ^
a.cc:23:33: note: previous declaration as 'Edge e [1000010]'
   23 | struct Edge { int u, v; ll w; } e[N]; int m;
      |                                 ^
a.cc:103:43: error: redefinition of 'int m'
  103 | struct Edge { int u, v; ll w; } e[N]; int m;
      |                                           ^
a.cc:23:43: note: 'int m' previously declared here
   23 | struct Edge { int u, v; ll w; } e[N]; int m;
      |                                           ^
a.cc:104:13: error: redefinition of 'bool operator<(const Edge&, const Edge&)'
  104 | inline bool operator < (const Edge &a, const Edge &b) { return a.w < b.w; }
      |             ^~~~~~~~
a.cc:24:13: note: 'bool operator<(const Edge&, const Edge&)' previously defined here
   24 | inline bool operator < (const Edge &a, const Edge &b) { return a.w < b.w; }
      |             ^~~~~~~~
a.cc:106:6: error: redefinition of 'void getrt(int, int)'
  106 | void getrt(int u, int fa) {
      |      ^~~~~
a.cc:26:6: note: 'void getrt(int, int)' previously defined here
   26 | void getrt(int u, int fa) {
      |      ^~~~~
a.cc:115:5: error: redefinition of 'int P'
  115 | int P; ll val, ans;
      |     ^
a.cc:35:5: note: 'int P' previously declared here
   35 | int P; ll val, ans;
      |     ^
a.cc:115:11: error: redefinition of 'll val'
  115 | int P; ll val, ans;
      |           ^~~
a.cc:35:11: note: 'll val' previously declared here
   35 | int P; ll val, ans;
      |           ^~~
a.cc:115:16: error: redefinition of 'll ans'
  115 | int P; ll val, ans;
      |                ^~~
a.cc:35:16: note: 'll ans' previously declared here
   35 | int P; ll val, ans;
      |                ^~~
a.cc:117:6: error: redefinition of 'void dfs(int, int, ll)'
  117 | void dfs(int u, int fa, ll dep) {
      |      ^~~
a.cc:37:6: note: 'void dfs(int, int, ll)' previously defined here
   37 | void dfs(int u, int fa, ll dep) {
      |      ^~~
a.cc:124:6: error: redefinition of 'void Link(int, int, ll)'
  124 | void Link(int u, int fa, ll dep) {
      |      ^~~~
a.cc:44:6: note: 'void Link(int, int, ll)' previously defined here
   44 | void Link(int u, int fa, ll dep) {
      |      ^~~~
a.cc:131:6: error: redefinition of 'void doit(int)'
  131 | void doit(int u) {
      |      ^~~~
a.cc:51:6: note: 'void doit(int)' previously defined here
   51 | void doit(int u) {
      |      ^~~~
a.cc:140:12: error: redefinition of 'int find(int)'
  140 | inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
      |            ^~~~
a.cc:60:12: note: 'int find(int)' previously defined here
   60 | inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
      |            ^~~~
a.cc:141:5: error: redefinition of 'int main()'
  141 | int main () {
      |     ^~~~
a.cc:61:5: note: 'int main()' previously defined here
   61 | int main () {
      |     ^~~~