Submission #901657

#	Time	Username	Problem	Language	Result	Execution time	Memory
901657		Hakiers	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	181 ms	39736 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int BASE = 1 << 18;
constexpr int MAXN = 1e5+7;
vector<int> G[MAXN];
ll TREE[BASE<<1][2];
vector<tuple<int, int, int>> event[MAXN];
int dp[MAXN][2];
int pre[MAXN], post[MAXN];
int depth[MAXN];
int jmp[MAXN][18];
int tajm;
int n, m;

void update(int v, ll val, bool x){
	v += BASE;
	TREE[v][x] = val;
	v/=2;
	while(v>0){
		TREE[v][x] = TREE[2*v][x] + TREE[2*v+1][x];
		v/=2;
	}
}

ll query(int a, int b, bool x){
	a += BASE-1;
	b += BASE+1;
	ll out = 0;
	while(a/2 != b/2){
		if(a%2 == 0) out += TREE[a+1][x];
		if(b%2 == 1) out += TREE[b-1][x];
		a/=2; b/=2;
	}
	return out;
} 

int lca(int v, int u){
	if(depth[u] < depth[v]) swap(u, v);
	
	for(int k = 17; k >= 0; k--)
		if(depth[jmp[u][k]] >= depth[v]) u = jmp[u][k];
	
	if(u == v) return v;
	
	for(int k = 17; k >= 0; k--){
		if(jmp[u][k] != jmp[v][k]){
			u = jmp[u][k];
			v = jmp[v][k];
		}
	}
	
	return jmp[v][0];
}

void dfs(int v, int p){
	depth[v] = depth[p]+1;
	pre[v] = ++tajm;
	jmp[v][0] = p;
	for(int k = 1; k <= 17; k++)
		jmp[v][k] = jmp[jmp[v][k-1]][k-1];
	
	for(auto u : G[v]){
		if(u == p) continue;
		dfs(u, v);
	}
	
	post[v] = ++tajm;
}

void dfs2(int v, int p){
	
	for(auto u : G[v]){
		if(u == p) continue;
		dfs2(u, v);
		dp[v][0] += dp[u][1];
	}
	dp[v][1] = dp[v][0];
	
	for(auto [a, b, c] : event[v]){
		ll path1 = query(pre[v], pre[a], 0) - query(pre[v], pre[a], 1);
		ll path2 = query(pre[v], pre[b], 0) - query(pre[v], pre[b], 1);
		dp[v][1] = max((ll)dp[v][1], (ll)dp[v][0] + c + path1 + path2);
	}
	
	update(pre[v], dp[v][0], 0);
	update(post[v], -dp[v][0], 0);
	update(pre[v], dp[v][1], 1);
	update(post[v], -dp[v][1], 1);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 1);
	cin >> m;
	for(int i = 1; i <= m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		event[lca(a, b)].push_back({a, b, c});
	}
	dfs2(1, 1);
	cout << dp[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