Submission #32936

#	Time	Username	Problem	Language	Result	Execution time	Memory
32936		aome	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	959 ms	34152 KiB

election_campaign

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

const int N = 100005;

struct Go {
	int u, v, w;

	Go (int u, int v, int w) :
		u(u), v(v), w(w) {}
};

int n, m, cnt;
int st[N], ed[N];
int h[N], p[20][N];
int f[2][N];
int it[4 * N];
int lazy[4 * N];
vector<int> G[N];
vector<Go> go[N];

void dfs(int u) {
	st[u] = ++cnt;
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		p[0][v] = u, h[v] = h[u] + 1, dfs(v);
	}
	ed[u] = cnt;
}

void push(int i, int l, int r) {
	if (!lazy[i]) return;
	if (l == r) it[i] += lazy[i];
	else lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
	lazy[i] = 0;
}

void upd(int i, int l, int r, int u, int v, int x) {
	push(i, l, r);
	if (l > v || u > r) return;
	if (u <= l && r <= v) {
		lazy[i] = x, push(i, l, r); return;
	}
	int mid = (l + r) >> 1;
	upd(i << 1, l, mid, u, v, x);
	upd(i << 1 | 1, mid + 1, r, u, v, x);
}

int get(int i, int l, int r, int p) {
	push(i, l, r);
	if (l == r) return it[i];
	int mid = (l + r) >> 1;
	if (mid >= p) return get(i << 1, l, mid, p);
	return get(i << 1 | 1, mid + 1, r, p);
}

void solve(int u) {
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		solve(v), f[0][u] += f[1][v];
	}
	f[1][u] = f[0][u];
	for (auto i : go[u]) {
		int cur = f[0][u] + i.w;
		if (i.u != u) {
			int x = i.u;
			for (int i = 17; i >= 0; --i) {
				if (h[p[i][x]] > h[u]) x = p[i][x];
			}
			cur += get(1, 1, n, st[i.u]) + f[0][i.u] - f[1][x];
		}
		if (i.v != u) {
			int x = i.v;
			for (int i = 17; i >= 0; --i) {
				if (h[p[i][x]] > h[u]) x = p[i][x];
			}
			cur += get(1, 1, n, st[i.v]) + f[0][i.v] - f[1][x];
		}
		f[1][u] = max(f[1][u], cur);
	}
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		upd(1, 1, n, st[v], ed[v], f[0][u] - f[1][v]);
	}
}

int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = 17; i >= 0; --i) {
		if (h[p[i][v]] >= h[u]) v = p[i][v];
	}
	for (int i = 17; i >= 0; --i) {
		if (p[i][v] != p[i][u]) v = p[i][v], u = p[i][u];
	}
	return (u == v) ? u : p[0][u];
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < (n - 1); ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	p[0][1] = h[1] = 1, dfs(1);
	for (int i = 1; i <= 17; ++i) {
		for (int j = 1; j <= n; ++j) {
			p[i][j] = p[i - 1][p[i - 1][j]];
		}
	}
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		go[lca(u, v)].push_back(Go(u, v, w));
	}
	solve(1); cout << f[1][1] << '\n';
}

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