Submission #363767

#	Time	Username	Problem	Language	Result	Execution time	Memory
363767		Bill_00	Election Campaign (JOI15_election_campaign)	C++14	0 / 100	208 ms	20644 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{
	int x,y,votes;
};

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

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

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

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

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

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

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

void update(int id,int l,int r,int x,int val){
	if(l==r){
		tree[id]=val;
		return;
	}
	int 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];
}

int p(int a,int 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[a][0],b);
}

void solve(int node,int par=1){
	for(int x:adj[node]){
		if(x!=par){
			solve(x,node);
			out[node]+=in[x];
			in[node]=max(in[node],in[x]);
		} 
	}
	for(plan xx:path[node]){
		int a=xx.x;
		int b=xx.y;
		int c=xx.votes;
		// in[node]=max(in[node],p(a,node)+p(b,node)+c+out[node]);
		while(a!=node){
			c+=out[a];
			c-=in[a];
			a=up[a][0];
		}
		while(b!=node){
			c+=out[a];
			c-=in[a];
			b=up[b][0];
		}
		c+=out[node];
		in[node]=max(in[node],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--){
		int a,b,c;
		cin >> a >> b >> c;
		int x=lca(a,b);
		path[x].pb({a,b,c});
	}
	solve(1);
	cout << in[1];
}

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