Submission #1034262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034262		juicy	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	172 ms	29520 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, LG = 17;

int n, m;
int pr[LG][N], s[N], dp[N], L[N], R[N], dep[N];
vector<int> g[N];
vector<array<int, 3>> cands[N];

void upd(int i, int x) {
	for (; i <= n; i += i & -i) {
		s[i] += x;
	}
}

void upd(int l, int r, int x) {
	upd(l, x);
	upd(r + 1, -x);
}

int qry(int i) {
	int res = 0;
	for (; i; i -= i & -i) {
		res += s[i];
	}
	return res;
}

int timer;

void pre_dfs(int u) {
	L[u] = ++timer;
	for (int v : g[u]) {
		if (v != pr[0][u]) {
			dep[v] = dep[u] + 1;
			pr[0][v] = u;
			for (int j = 1; j < LG; ++j) {
				pr[j][v] = pr[j - 1][pr[j - 1][v]];
			}
			pre_dfs(v);
		}
	}
	R[u] = timer;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int j = LG - 1; ~j; --j) {
		if (dep[u] - (1 << j) >= dep[v]) {
			u = pr[j][u];
		} 
	}
	if (u == v) {
		return u;
	} 
	for (int j = LG - 1; ~j; --j) {
		if (pr[j][u] != pr[j][v]) {
			u = pr[j][u], v = pr[j][v];
		}
	}
	return pr[0][u];
}

void dfs(int u) {
	int sum = 0;
	for (int v : g[u]) {
		if (v != pr[0][u]) {
			dfs(v);
			sum += dp[v];
		}
	}
	dp[u] = sum;
	for (auto [x, y, w] : cands[u]) {
		dp[u] = max(dp[u], qry(L[x]) + qry(L[y]) + w + sum);
	}
	upd(L[u], R[u], sum - dp[u]);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}	
	pre_dfs(1);
	cin >> m;
	while (m--) {
		int u, v, w; cin >> u >> v >> w;
		cands[lca(u, v)].push_back({u, v, w});
	}
	dfs(1);
	cout << dp[1];
	return 0;
}

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