Submission #300595

#	Time	Username	Problem	Language	Result	Execution time	Memory
300595		hexan	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	373 ms	28152 KiB

election_campaign

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

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)

const int N = (1 << 17);
vector<int> g[N];
int sz[N], dth[N], pa[N];

void dfs(int v, int p) {
	sz[v] = 1;
	for(int to : g[v]) {
		if (to == p) continue;
		pa[to] = v;
		dth[to] = dth[v] + 1;
		dfs(to, v);
		sz[v] += sz[to];
	}
	for(int i = 1; i < size(g[v]); i++) {
		if (g[v][i] == p) continue;
		if (g[v][0] == p || sz[g[v][0]] < sz[g[v][i]]) {
			swap(g[v][0], g[v][i]);
		}
	}
}

int tt = 0;
int id[N], rid[N];
int head[N];

void dfs2(int v, int p, int h) {
	head[v] = h;
	id[v] = tt++;
	rid[id[v]] = v;
	for(int to : g[v]) {
		if (to != p) {
			if (to == g[v][0]) {
				dfs2(to, v, h);
			} else {
				dfs2(to, v, to);
			}
		}
	}
}

int n;
ll t[2 * N];

void upd(int v, int val) {
	v += N - 1;
	t[v] += val;
	while (v > 0) {
		v = (v - 1) >> 1;
		t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	}
}

ll get(int v, int tl, int tr, int l, int r) {
	if (l >= r) return 0;
	if (tl == l && tr == r) return t[v];
	int tm = (tl + tr) / 2;
	return get(v * 2 + 1, tl, tm, l, min(r, tm)) + get(v * 2 + 2, tm, tr, max(l, tm), r);
}

ll get(int l, int r) {
	return get(0, 0, N, l, r + 1);
}

ll sum(int p, int x) {
	ll res = 0;
	while (head[p] != head[x]) {
		res += get(id[head[x]], id[x]);
		x = pa[head[x]];
	}
	res += get(id[p], id[x]);
	return res;
}


int lca(int a, int b) {
	while (1) {
		if (head[a] == head[b]) {
			if (dth[a] < dth[b]) return a;
			else return b;
		}
		if (dth[head[a]] < dth[head[b]]) swap(a, b);
		a = pa[head[a]];
	}
}

int a1[N], b1[N], c[N];
vector<int> e[N];
ll dp[N];
ll cur[N];

void Do(int v, int p) {
	for(int to : g[v]) {
		if (to != p) {
			Do(to, v);
		}
	}
	for(int to : g[v]) {
		if (to != p) {
			dp[v] += dp[to];
		}
	}
	for(int x : e[v]) {
		int a = a1[x], b = b1[x];
		chkmax(dp[v], sum(v, a) + sum(v, b) - cur[v] + c[x]);
	}
	if (p != -1) {
		cur[p] += dp[v];
		upd(id[p], dp[v]);
		upd(id[v], -dp[v]);
	}
}

void run() {
	cin >> n;
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0, -1);
	dfs2(0, -1, 0);
	int m;
	cin >> m;
	for(int i = 0; i < m; i++) {
		cin >> a1[i] >> b1[i] >> c[i];
		--a1[i]; --b1[i];
		e[lca(a1[i], b1[i])].push_back(i);
	}
	Do(0, -1);
	cout << dp[0];
}

int main() {
#ifdef LOCAL
	freopen("input", "r", stdin);
	freopen("output", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	run();
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40