Submission #872218

#	Time	Username	Problem	Language	Result	Execution time	Memory
872218		serifefedartar	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	146 ms	32596 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 100;

vector<vector<int>> graph;
vector<pair<pair<int,int>, int>> plan[MAXN];
int tin[MAXN], tout[MAXN], T = 0;
int up[LOGN][MAXN], depth[MAXN], dp[MAXN];
int fen_node[MAXN], fen_subs[MAXN];
int get_node(int k) {
	int res = 0;
	while (k > 0) {
		res += fen_node[k];
		k -= k & -k;
	}
	return res;
}

int get_subs(int k) {
	int res = 0;
	while (k > 0) {
		res += fen_subs[k];
		k -= k & -k;
	}
	return res;
}

void add_node(int k, int val) {
	while (k < MAXN) {
		fen_node[k] += val;
		k += k & -k;
	}
}

void add_subs(int k, int val) {
	while (k < MAXN) {
		fen_subs[k] += val;
		k += k & -k;
	}
}

void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		depth[u] = depth[node] + 1;
		up[0][u] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u] = up[i-1][up[i-1][u]];
		dfs(u, node);
	}
	tout[node] = T;
}

int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);

	if (a == b)
		return a;
	for (int i = LOGN - 1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b];
		}
	}
	return up[0][a];
}

void dfs2(int node, int parent) {
	int sum = 0;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs2(u, node);
		sum += dp[u];
	}

	dp[node] = sum;
	for (auto u : plan[node]) {
		int now = get_subs(tin[u.f.f]) + get_subs(tin[u.f.s]) - 2 * get_subs(tin[node]) + get_subs(tin[node]) - (node == 1 ? 0 : get_subs(tin[parent]));
		now -= get_node(tin[u.f.f]) + get_node(tin[u.f.s]) - 2 * get_node(tin[node]);
		dp[node] = max(dp[node], now + u.s);
	}
	add_node(tin[node], dp[node]);
	add_node(tout[node]+1, -dp[node]);
	if (node != 1) {
		add_subs(tin[parent], dp[node]);
		add_subs(tout[parent]+1, -dp[node]);
	}
}

int main() {
	fast
	int N, M, a, b, c;
	cin >> N;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i < N; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1;
	dfs(1, 1);

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		plan[lca(a, b)].push_back({{a, b}, c});
	}
	dfs2(1, 1);
	cout << dp[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