Submission #240007

#	Time	Username	Problem	Language	Result	Execution time	Memory
240007		Knps4422	Election Campaign (JOI15_election_campaign)	C++14	0 / 100	188 ms	23640 KiB

election_campaign

//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
 
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(ll x = 1 ; x <= y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);

using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
const int nmax = 100005;
const ll linf = 1e17;
const ll mod = 1e9+7;
const int inf = 1e9+7;
const ll lim = 1e4;

int n,m;
vec <int> g[nmax];
int tin[nmax], tout[nmax],tt=1;
int up[nmax][20];
vec < pair < pii , ll > > pth[nmax];
vec < int > vc;

void dfs(int nod, int par){
	up[nod][0] = par;
	tin[nod] = ++tt;
	for(int j : g[nod]){
		if(j != par)
		dfs(j,nod);
	}
	tout[nod] = ++tt;
}

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

int lca(int a,  int b){
	if(anc(a,b))return a;
	int p = a;
	for(int i = 16 ; i >= 0; i--){
		if(!anc(up[p][i],b)) p = up[p][i];
	}
	return up[p][0];
}

struct {
	ll bit[2*nmax];
	ll query(int pos){
		ll r = 0;
		for(;pos > 0; pos -= pos&-pos){
			r += bit[pos];
		}
		return r;
	}
	void update(int pos , int val){
		for(;pos <= tt ; pos += pos&-pos){
			bit[pos] += val;
		}
	}
	ll range_query(int l , int r){
		return query(r) - query(l-1);
	}

}bt1,bt2;
ll dp[nmax];

void dfs2(int nod, int par){
	for(int j : g[nod]){
		if(j != par)
				dfs2(j,nod);
	}
	ll r = 0;
	for(int j : g[nod]){
		if(j == par)continue;
		r += dp[j];
	}
	ll rez = r;
	bt1.update(tin[nod],r);
	bt2.update(tout[nod],r);
	for(auto path : pth[nod]){
		rez = max( rez, bt1.range_query(tin[nod],tin[path.fr.fr]) - bt2.range_query(tin[nod],tin[path.fr.fr]) 
			+bt1.range_query(tin[nod],tin[path.fr.sc]) - bt2.range_query(tin[nod],tin[path.fr.sc]) - r + path.sc );
	}
	dp[nod] = rez;
	bt1.update(tin[nod],-dp[nod]);
	bt2.update(tout[nod],-dp[nod]);
	cout << nod << ' ' << dp[nod] << '\n';
}
int main(){
	fast;
	cin >> n;
	forn(i,n-1){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1,1);

	for(int i = 1 ; i < 20 ; i++){
		forn(ii,n){
			up[ii][i] = up[up[ii][i-1]][i-1];
		}
	}
	cin >> m;
	forn(i,m){
		int a, b, c;
		cin >> a >> b >> c;
		pth[lca(a,b)].pb({{a,b},c});
	}
	dfs2(1,1);
	cout << dp[1] << '\n';
}

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