Submission #160237

#	Time	Username	Problem	Language	Result	Execution time	Memory
160237		iefnah06	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	304 ms	29688 KiB

election_campaign

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

const int MAXN = 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 lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	int d = depth[a] - depth[b];
	for (int i = 0; (1 << i) <= d; i++) {
		if (d & (1 << i)) {
			a = par[a][i];
		}
	}
	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(par[a][0] == par[b][0]);
	assert(a != b);
	return par[a][0];
}

struct bit {
	int a[MAXN];

	bit() {
		memset(a, 0, sizeof(a));
	}

	void update(int i, int v) {
		for (i++; i <= N; i += (i & -i)) {
			a[i] += v;
		}
	}

	void update(int l, int r, int v) { // half open
		update(l, +v);
		update(r, -v);
	}

	int query(int i) { // value at i-th position
		int ans = 0;
		for (i++; i; i -= (i & -i)) {
			ans += a[i];
		}
		return ans;
	}
} bestsum, chsum;

vector<array<int, 3>> paths[MAXN];
int st[MAXN];
int en[MAXN];
int curind = 0;

int dfs(int cur) {
	st[cur] = curind++;
	int ch = 0;
	for (int nxt : adj[cur]) {
		ch += dfs(nxt);
	}
	en[cur] = curind;

	int best = ch;
	for (auto it : paths[cur]) {
		int val = ch + it[2];
		if (it[0] != cur) {
			val -= bestsum.query(st[it[0]]);
			val += chsum.query(st[it[0]]);
		}
		assert(it[1] != cur);
		val -= bestsum.query(st[it[1]]);
		val += chsum.query(st[it[1]]);
		best = max(best, val);
	}
	bestsum.update(st[cur], en[cur], best);
	chsum.update(st[cur], en[cur], ch);

	return best;
}

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});
	}

	cout << dfs(1) << '\n';

	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