Submission #160229

#	Time	Username	Problem	Language	Result	Execution time	Memory
160229		iefnah06	Election Campaign (JOI15_election_campaign)	C++11	10 / 100	190 ms	30428 KiB

election_campaign

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

const int MAXN = 1.1e5;
const int MAXM = 1.1e5;
int N, M;
vector<int> adj[MAXN];

int par[MAXN][20];
int depth[MAXN];

void dfs_par(int cur, int prv) {
	if (prv) {
		adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv));
	}
	par[cur][0] = prv;
	for (int i = 0; par[cur][i]; i++) {
		par[cur][i+1] = par[par[cur][i]][i];
	}
	for (int nxt : adj[cur]) {
		depth[nxt] = depth[cur] + 1;
		dfs_par(nxt, cur);
	}
}

int lift(int a, int d) {
	assert(d >= 0);
	for (int i = 0; (1 << i) <= d; i++) {
		if (d & (1 << i)) {
			a = par[a][i];
		}
	}
	return a;
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	a = lift(a, depth[a] - depth[b]);
	assert(depth[a] == depth[b]);
	if (a == b) return a;
	int i = 0;
	while (par[a][i]) i++;
	while (i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	assert(a != b);
	assert(par[a][0] == par[b][0]);
	return par[a][0];
}

int getchild(int a, int b) {
	assert(depth[a] < depth[b]);
	int c = lift(b, depth[b] - depth[a] - 1);
	assert(par[c][0] == a);
	return c;
}

vector<array<int, 3>> paths[MAXN];
int dp[MAXN];
int chsum[MAXN];

int dfs(int cur) {
	for (int nxt : adj[cur]) {
		chsum[cur] += dfs(nxt);
	}
	int ans = chsum[cur];
	for (auto it : paths[cur]) {
		int val = chsum[cur] + it[2];
		if (cur != it[0]) {
			val += chsum[it[0]];
			val -= dp[getchild(cur, it[0])];
		}
		assert(cur != it[1]);
		val += chsum[it[1]];
		val -= dp[getchild(cur, it[1])];
		ans = max(ans, val);
	}
	return dp[cur] = ans;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs_par(1, 0);
	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (depth[a] > depth[b]) swap(a, b);
		paths[lca(a, b)].push_back({a, b, c});
	}
	
	int ans = dfs(1);
	cout << ans << '\n';

	return 0;
}

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