Submission #519543

#	Time	Username	Problem	Language	Result	Execution time	Memory
519543		valerikk	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	174 ms	52648 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 10;
const int K = 20;

struct {
	ll t[(int) 1e6 + 10];

	void upd(int ind, ll val) {
		for (int i = ind + 1; i < N; i += i & -i) {
			t[i] += val;
		}
	}

	void upd(int l, int r, ll val) {
		upd(l, val);
		upd(r, -val);
	}

	ll get(int ind) {
		ll sum = 0;
		for (int i = ind + 1; i > 0; i -= i & -i) {
			sum += t[i];
		}
		return sum;
	}
} fsum, fdp;

int n;
vector<int> g[N];
int m;
int a[N], b[N];
ll c[N];

int tin[N], tout[N];
int par[N];
int up[K][N];

void dfs(int v, int p) {
	static int t = 0;
	tin[v] = t++;
	par[v] = p;

	if (p != v) {
		g[v].erase(find(g[v].begin(), g[v].end(), p));
	}

	for (int u : g[v]) {
		dfs(u, v);
	}
	
	tout[v] = t;
}

bool anc(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int getlca(int v, int u) {
	if (anc(v, u)) {
		return v;
	}
	if (anc(u, v)) {
		return u;
	}

	for (int i = K - 1; i >= 0; i--) {
		if (!anc(up[i][v], u)) {
			v = up[i][v];
		}
	}
	return par[v];
}

vector<int> by_lca[N];
ll dp[N];
ll sum[N];

void dfsdp(int v) {
	for (int u : g[v]) {
		dfsdp(u);
		sum[v] += dp[u];
	}

	dp[v] = sum[v];
	for (int i : by_lca[v]) {
		ll cur = fsum.get(tin[a[i]]) + fsum.get(tin[b[i]]) + sum[v] - fdp.get(tin[a[i]]) - fdp.get(tin[b[i]]) + c[i];
		dp[v] = max(dp[v], cur);
	}

	fsum.upd(tin[v], tout[v], sum[v]);
	fdp.upd(tin[v], tout[v], dp[v]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--;
		b[i]--;
	}

	dfs(0, 0);

	for (int i = 0; i < n; i++) {
		up[0][i] = par[i];
	}
	for (int i = 1; i < K; i++) {
		for (int j = 0; j < n; j++) {
			up[i][j] = up[i - 1][up[i - 1][j]];
		}
	}

	for (int i = 0; i < m; i++) {
		by_lca[getlca(a[i], b[i])].push_back(i);
	}

	dfsdp(0);

	cout << dp[0] << "\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