Submission #363799

#	Time	Username	Problem	Language	Result	Execution time	Memory
363799		Bill_00	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	508 ms	47112 KiB

election_campaign

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define N 100001
typedef long long ll;
const long long MOD=1000000007;
using namespace std;
struct plan{
	ll x,y,votes;
};

ll timer,m,n,l,k,sz[N],h[N],seg[N];
ll tin[N],tout[N],up[N][20];
ll in[N],out[N],tree[4*N+4];

vector<plan>path[N];
vector<ll>adj[N];

void dfs(ll node,ll par=1){
	tin[node]=++timer;
	up[node][0]=par;
	for(ll i=1;i<=l;i++){
		up[node][i]=up[up[node][i-1]][i-1];
	}
	sz[node]=1;
	for(ll x:adj[node]){
		if(x!=par){
			dfs(x,node);
			sz[node]+=sz[x];
		} 
	}
	tout[node]=++timer;
}

void dfs1(ll node,ll par,ll head){
	seg[node]=++k;
	h[node]=head;
	pair<ll,ll>bigchild={0,-1};
	for(ll x:adj[node]){
		if(x!=par) bigchild=max(bigchild,{sz[x],x});
	}
	if(bigchild.ss!=-1) dfs1(bigchild.ss,node,head);
	for(ll x:adj[node]){
		if(x!=par && x!=bigchild.ss) dfs1(x,node,x);
	}
}

bool is(ll a,ll b){
	return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}

ll lca(ll a,ll b){
	if(is(a,b)) return a;
	if(is(b,a)) return b;
	for(ll i=l;i>=0;i--){
		if(!is(up[a][i],b)) a=up[a][i];
	}
	return up[a][0];
}

ll query(ll id,ll l,ll r,ll L,ll R){
	if(r<L || R<l) return 0;
	if(L<=l && r<=R) return tree[id];
	ll m=(l+r)>>1;
	return query(id*2,l,m,L,R)+query(id*2+1,m+1,r,L,R);
}

void update(ll id,ll l,ll r,ll x,ll val){
	if(l==r){
		tree[id]=val;
		return;
	}
	ll m=(l+r)>>1;
	if(m>=x) update(id*2,l,m,x,val);
	else update(id*2+1,m+1,r,x,val);
	tree[id]=tree[id*2]+tree[id*2+1];
}

ll p(ll a,ll b){
	if(is(h[a],b)) return query(1,1,k,seg[b],seg[a]);
	return query(1,1,k,seg[h[a]],seg[a])+p(up[h[a]][0],b);
}

void solve(ll node,ll par=1){
	for(ll x:adj[node]){
		if(x!=par){
			solve(x,node);
			out[node]+=in[x];
		} 
	}
	in[node]=out[node];
	for(plan xx:path[node]){
		ll a=xx.x;
		ll b=xx.y;
		ll c=xx.votes;
		in[node]=max(in[node],p(a,node)+p(b,node)+c+out[node]);
	}
	update(1,1,k,seg[node],out[node]-in[node]);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	l=ceil(log2(n));
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}	
	dfs(1);
	dfs1(1,1,1);
	cin >> m;
	while(m--){
		ll a,b,c;
		cin >> a >> b >> c;
		ll x=lca(a,b);
		path[x].pb({a,b,c});
	}
	solve(1);
	cout << in[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