Submission #518882

#	Time	Username	Problem	Language	Result	Execution time	Memory
518882		amunduzbaev	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	232 ms	36716 KiB

election_campaign

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

#define ar array

const int N = 1e5 + 5;
vector<int> edges[N], qq[N];
int par[N][20], tin[N], tout[N], t;
int dp[N], p[N][3];

struct BIT{
	int tree[N];
	
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int c=0;
		for(;i>0;i-=(i&-i)) c += tree[i];
		return c;
	}
}tree;

void dfs(int u, int p = -1){
	tin[u] = ++t;
	for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
	for(auto x : edges[u]){
		if(x == p) continue;
		par[x][0] = u;
		dfs(x, u);
	} tout[u] = t;
}
bool is(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int lca(int a, int b){
	if(is(a, b)) return a;
	if(is(b, a)) return b;
	for(int i=19;~i;i--){
		if(!is(par[a][i], b)) a = par[a][i];
	} return par[a][0];
}

int first(int a, int b){
	assert(is(a, b));
	for(int i=19;~i;i--){
		if(!is(par[b][i], a)) b = par[b][i];
	} 
	assert(par[b][0] == a);
	return b;
}

void dpdfs(int u, int pp = -1){
	int tot = 0;
	for(auto x : edges[u]){
		if(x == pp) continue;
		dpdfs(x, u);
		tot += dp[x];
	} dp[u] = tot;
	
	for(auto i : qq[u]){
		if(p[i][0] == u){
			int f = first(u, p[i][1]);
			dp[u] = max(dp[u], tree.get(tin[p[i][1]]) + tot - dp[f] + p[i][2]);
		} else if(p[i][1] == u){
			int f = first(u, p[i][0]);
			dp[u] = max(dp[u], tree.get(tin[p[i][0]]) + tot - dp[f] + p[i][2]);
		} else {
			int a = first(u, p[i][0]), b = first(u, p[i][1]);
			dp[u] = max(dp[u], tree.get(tin[p[i][0]]) + tree.get(tin[p[i][1]]) + tot - dp[a] - dp[b] + p[i][2]);
		}
	}
	
	for(auto x : edges[u]){
		if(x == pp) continue;
		tree.add(tin[x], tot - dp[x]);
		tree.add(tout[x] + 1, dp[x] - tot);
	} tree.add(tin[u], tot); tree.add(tin[u] + 1, -tot);
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	par[1][0] = 1;
	dfs(1);
	
	int m; cin>>m;
	for(int i=0;i<m;i++){
		cin>>p[i][0]>>p[i][1]>>p[i][2];
		//~ cout<<lca(p[i][0], p[i][1])<<"\n";
		qq[lca(p[i][0], p[i][1])].push_back(i);
	}
	
	dpdfs(1);
	cout<<dp[1]<<"\n";
	//~ for(int i=1;i<=n;i++) cout<<dp[i]<<"\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