Submission #157396

#	Time	Username	Problem	Language	Result	Execution time	Memory
157396		nvmdava	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	263 ms	34488 KiB

election_campaign

#include <bits/stdc++.h>
#define N 131072
using namespace std;
#define ll long long
#define ff first
#define ss second

struct Seg{
	ll val[N << 1];
	
	void update(int L, int R, ll v, int id = 1, int l = 1, int r = N){
		if(L <= l && r <= R){
			val[id] += v;
			return;
		}
		if(r < L || l > R){
			return;
		}
		
		int m = (l + r) >> 1;
		update(L, R, v, id << 1, l, m);
		update(L, R, v, id << 1 | 1, m + 1, r);
	}
	
	inline ll get(int v){
		v += N - 1;
		ll s = 0;
		while(v){
			s += val[v];
			v >>= 1;
		}
		return s;
	}
} child;

vector<int> adj[N];

int in[N], out[N], p[N][20];
int d[N];

int n;
int cnt;

void dfs2(int v, int par){
	in[v] = ++cnt;
	
	d[v] = d[par] + 1;
	p[v][0] = par;
	
	for(int i = 0; p[v][i] != 0; i++){
		p[v][i + 1] = p[p[v][i]][i];	
	}
	
	for(int& x : adj[v]){
		if(x == par) continue;
		dfs2(x, v);
	}
	
	out[v] = cnt;
}

int find(int v, int u){
	if(d[v] < d[u]) swap(v, u);
	
	for(int i = 0; d[v] - d[u]; i++)
		if((d[v] - d[u]) & (1 << i))
			v = p[v][i];	
	
	if(v == u) return v;
	for(int i = 18; i >= 0; i--){
		if(p[v][i] != p[u][i]){
			v = p[v][i];
			u = p[u][i];
		}
	}
	return p[v][0];
}

vector<pair<pair<int, int>, int> > obj[N];

ll is1[N], is0[N];

void dfs(int v, int p){
	ll res = 0, tmp;
	
	for(int& x : adj[v]){
		if(x == p) continue;
		dfs(x, v);
		res += is1[x];
	}
	
	is1[v] = is0[v] = res;
	
	
	for(auto& x : obj[v]){
		tmp = x.ss + res;
		tmp += child.get(in[x.ff.ff]);
		tmp += child.get(in[x.ff.ss]);
		is1[v] = max(is1[v], tmp);
	}
	child.update(in[v], out[v], res - is1[v]);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	
	for(int v, u, i = 1; i < n; i++){
		cin>>v>>u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	
	dfs2(1, 0);
	
	cin>>n;
	while(n--){
		int a, b, c;
		cin>>a>>b>>c;
		obj[find(a, b)].push_back({{a, b}, c});
	}
	
	dfs(1, 0);
	
	cout<<is1[1];
}

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