Submission #484125

#	Time	Username	Problem	Language	Result	Execution time	Memory
484125		S2speed	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	243 ms	65764 KiB

election_campaign

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 2e5 + 16 , md = 1e9 + 7 , inf = 2e9;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

struct fentree {

	ll sz;
	vector<ll> val;

	void init(ll n){
		sz = n;
		val.assign(sz , 0);
		return;
	}

	void add(ll i , ll k){
		ll h = i;
		while(h < sz){
			val[h] += k;
			h |= (h + 1);
		}
		return;
	}

	ll cal(ll i){
		ll h = i , res = 0;
		while(h > -1){
			res += val[h];
			h &= (h + 1); h--;
		}
		return res;
	}

};

fentree ff , fd;
ll f[maxn] , dp[maxn];
vector<ll> adj[maxn] , a[maxn];
ll v[maxn] , u[maxn] , c[maxn];
ll jad[maxn][20] , pr[maxn] , dis[maxn] , dep = 0 , bt[maxn] , ft[maxn] , tme = 0;

void pDFS(ll r , ll par){
	jad[r][0] = pr[r] = par;
	for(ll j = 1 ; j < 20 ; j++){
		if(jad[r][j - 1] == -1) break;
		jad[r][j] = jad[jad[r][j - 1]][j - 1];
	}
	dis[r] = dep++;
	bt[r] = tme++;
	for(auto i : adj[r]){
		if(i == par) continue;
		pDFS(i , r);
	}
	ft[r] = tme;
	dis[r] = dep--;
	return;
}

ll find_jad(ll v , ll d){
	d = dis[v] - d;
	for(ll j = 0 ; j < 20 ; j++){
		if(d & (1 << j)){
			v = jad[v][j];
		}
	}
	return v;
}

ll lca(ll v , ll u){
	if(dis[v] > dis[u]) swap(v , u);
	u = find_jad(u , dis[v]);
	if(v == u) return v;
	for(ll j = 19 ; j >= 0 ; j--){
		if(jad[v][j] != jad[u][j]){
			v = jad[v][j]; u = jad[u][j];
		}
	}
	return pr[v];
}

void dDFS(ll r , ll par){
	for(auto i : adj[r]){
		if(i == par) continue;
		dDFS(i , r);
		dp[r] += dp[i];
	}
	f[r] = dp[r];
	for(auto j : a[r]){
		ll h = ff.cal(bt[v[j]]) + ff.cal(bt[u[j]]) + f[r] - fd.cal(bt[v[j]]) - fd.cal(bt[u[j]]) + c[j];
		dp[r] = max(dp[r] , h);
	}
	ff.add(bt[r] , f[r]); ff.add(ft[r] , -f[r]);
	fd.add(bt[r] , dp[r]); fd.add(ft[r] , -dp[r]);
	return;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	memset(dp , 0 , sizeof(dp));
	memset(jad , -1 , sizeof(jad));
	ll n , m;
	cin>>n;
	for(ll i = 1 ; i < n ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	pDFS(0 , -1);
	cin>>m;
	for(ll i = 0 ; i < m ; i++){
		cin>>v[i]>>u[i]>>c[i]; v[i]--; u[i]--;
		ll l = lca(v[i] , u[i]);
		a[l].push_back(i);
	}
	ff.init(n); fd.init(n);
	dDFS(0 , -1);
//	for(ll i = 0 ; i < n ; i++){
//		cout<<dp[i]<<' ';
//	}
//	cout<<'\n';
	cout<<dp[0]<<'\n';
	return 0;
}

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