Submission #960515

#	Time	Username	Problem	Language	Result	Execution time	Memory
960515		pcc	Election Campaign (JOI15_election_campaign)	C++17	30 / 100	1014 ms	40028 KiB

election_campaign

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt,sse4,avx2")


const int mxn = 1e5+10;
int N,Q;

vector<int> tree[mxn];
vector<pair<pii,int>> req[mxn];

namespace HLD{
	int idx[mxn],link_top[mxn],par[mxn],dep[mxn],bs[mxn],sz[mxn];
	ll bit[mxn];
	bitset<mxn> done;
	void modify(int p,ll v){
		done[p] = true;
		bit[p] = bit[p+1]+v;
		return;
		/*
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;

	   */
	}
	ll getval(int s,int e){
		if(!done[s])return bit[s+1]-bit[e+1];
		return bit[s]-bit[e+1];
		/*
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;

	   */
	}
	int cnt = 0;
	void dfs1(int now){
		sz[now] = 1;
		for(auto nxt:tree[now]){
			if(nxt == par[now])continue;
			par[nxt] = now;
			dep[nxt] = dep[now]+1;
			dfs1(nxt);
			if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
		}
		return;
	}
	void dfs2(int now,int top){
		idx[now] = ++cnt;
		link_top[now] = top;
		if(bs[now])dfs2(bs[now],top);
		for(auto nxt:tree[now]){
			if(nxt == par[now]||nxt == bs[now])continue;
			dfs2(nxt,nxt);
		}
		return;
	}
	pll LCA(int a,int b){
		pll re = pll(0,0);
		int ta = link_top[a],tb = link_top[b];
		while(ta != tb){
			if(dep[ta]<dep[tb]){
				swap(a,b);
				swap(ta,tb);
			}
			re.sc += getval(idx[ta],idx[a]);
			a = par[ta];ta = link_top[a];
		}
		if(idx[a]>idx[b])swap(a,b);
		re.sc += getval(idx[a],idx[b]);
		re.fs = a;
		return re;
	}
}

namespace CALC{
	ll ans = 0;
	ll sum[mxn],dp[mxn];
	void dfs(int now){
		sort(tree[now].begin(),tree[now].end(),[](int a,int b){return HLD::idx[a]>HLD::idx[b];});
		for(auto nxt:tree[now]){
			if(nxt == HLD::par[now])continue;
			dfs(nxt);
			sum[now] += dp[nxt];
		}
		dp[now] = max(dp[now],sum[now]);
		for(auto &i:req[now]){
			auto [a,b] = i.fs;
			int w = i.sc;
			ll ts = sum[now]+HLD::LCA(a,b).sc+w;
			dp[now] = max(dp[now],ts);
		}
		HLD::modify(HLD::idx[now],sum[now]-dp[now]);
	}
	void GO(){
		dfs(1);
		cout<<dp[1]<<'\n';
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	HLD::dfs1(1);
	HLD::dfs2(1,1);
	cin>>Q;
	while(Q--){
		int a,b,c;
		cin>>a>>b>>c;
		int h = HLD::LCA(a,b).fs;
		req[h].push_back(make_pair(pii(a,b),c));
	}
	CALC::GO();
}

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