제출 #1168174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168174		_rain_	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	228 ms	39216 KiB

election_campaign

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

class IT{
	public:
		vector<LL>st;
		#define lef(id) id*2
		#define rig(id) id*2+1
		void init(int _n){
			st.assign(_n*4+2,0);
		}
		void upd(int id,int l,int r,int pos,LL val){
			if (l>pos||r<pos) return;
			if (l==r) st[id]+=val;
			else{
				int m=(l+r)/2;
				upd(lef(id),l,m,pos,val);
				upd(rig(id),m+1,r,pos,val);
				st[id]=(st[lef(id)]+st[rig(id)]);
			}
		}
		LL Get(int id,int l,int r,int u,int v){
			if (l>v||r<u) return 0;
			if (u<=l&&r<=v) return st[id];
			int m=(l+r)/2;
			return (Get(lef(id),l,m,u,v)+Get(rig(id),m+1,r,u,v));
		}
};
IT tree;

const int N=(int)2e5;
const int MAXLOG=15;
vector<int>ke[N+2];
struct Node{
	int first,second,cost;
};
vector<Node>query[N+2];
int sta[N+2]={},fin[N+2]={},time_dfs=0;
int par[N+2][MAXLOG+2],h[N+2];
int n,q;


void dfs(int u,int p){
	par[u][0]=p;
	h[u]=h[p]+1;
	sta[u]=++time_dfs;
	for(int i=1;i<=MAXLOG;++i){
		par[u][i]=par[par[u][i-1]][i-1];
	}
	for(auto&v:ke[u]){
		if (v==p) continue;
		dfs(v,u);
	}
	fin[u]=time_dfs;
}

int LCA(int u,int v){
	if (h[u]<=h[v]) swap(u,v);
	for(int i=MAXLOG;i>=0;--i){
		if (h[par[u][i]]>=h[v]){
			u=par[u][i];
		}
	}
	if (u==v) return u;
	for(int i=MAXLOG;i>=0;--i){
		if (par[u][i]!=par[v][i]) {
			u=par[u][i],v=par[v][i];
		}
	}
	return par[u][0];
}


const LL INF=(LL)1e16;
LL dp[N+2];

void add_range(int u,LL val){
	tree.upd(1,1,time_dfs,sta[u],val);
	tree.upd(1,1,time_dfs,fin[u]+1,-val);
	return;
}
LL Get(int u){
	return tree.Get(1,1,time_dfs,1,sta[u]);
}

void calc(int u,int p){
	for(auto&v:ke[u]){
		if (v==p) continue;
		calc(v,u);
		dp[u]+=dp[v];
	}
	add_range(u,dp[u]);
	LL sum=dp[u];
	for(auto&v:query[u]){
		dp[u]=max(dp[u],sum+Get(v.first)+Get(v.second)-Get(u)*2+v.cost);
	}
	add_range(u,-dp[u]);
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
	cin>>n;
	tree.init(n);
	for(int i=2;i<=n;++i){
		int u,v; cin>>u>>v;
		ke[u].push_back(v);
		ke[v].push_back(u);
	} 	
	dfs(1,0);
	cin>>q;
	for(int i=1;i<=q;++i){
		int u,v,c; 
		cin>>u>>v>>c;
		int lca=LCA(u,v);
		query[lca].push_back({u,v,c});
	}
	calc(1,0);
	cout<<dp[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