제출 #1163841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163841		mertbbm	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	211 ms	67984 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

vector<int>adj[100005];
int in[100005];
int out[100005];
int d[100005];
int two[22][100005];
int ptr=0;

void dfs(int index, int par){
	in[index]=++ptr;
	for(int x=0;x<20;x++){
		two[x+1][index]=two[x][two[x][index]];
	}
	for(auto it:adj[index]){
		if(it==par) continue;
		d[it]=d[index]+1;
		two[0][it]=index;
		dfs(it,index);
	}
	out[index]=ptr;
}

int lca(int a, int b){
	if(d[a]>d[b]) swap(a,b);
	int diff=d[b]-d[a];
	for(int x=0;x<20;x++){
		if(diff&(1<<x)){
			b=two[x][b];
		}
	}
	if(a==b) return a;
	for(int x=19;x>=0;x--){
		if(two[x][a]!=two[x][b]){
			a=two[x][a];
			b=two[x][b];
		}
	}
	return two[0][a];
}

inline int combine(int a, int b){
	return max(a,b);
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	int lazyUpd;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyUpd(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void self_add(int x){
		v+=x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyUpd){
			l->self_add(lazyUpd);
			r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x>y) return 0;
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
}*root;

vector<pii>storage[100005];
vector<pair<pii,int>>storage2[100005];
int n;
int dp[2][100005];

void dfs2(int index, int par){
	vector<int>v;
	vector<int>v2;
	for(auto it:adj[index]){
		if(it==par) continue;
		dfs2(it,index);
		v.push_back(out[it]);
		v2.push_back(dp[1][it]);
		dp[0][index]+=dp[1][it];
	}
	
	sort(v.begin(),v.end());
	
	int best=0;
	for(auto it:storage[index]){
		int ptr=lower_bound(v.begin(),v.end(),in[it.first])-v.begin();
		int nxt=v2[ptr];
		int hold=dp[0][index]-nxt+dp[0][it.first]+it.second;
		hold+=root->query(in[it.first],in[it.first]);
		//show(hold,hold);
		best=max(best,hold);
	}
	
	for(auto it:storage2[index]){
		int a=it.first.first;
		int b=it.first.second;
		int ptr=lower_bound(v.begin(),v.end(),in[a])-v.begin();
		int nxt=v2[ptr];
		
		int ptr2=lower_bound(v.begin(),v.end(),in[b])-v.begin();
		int nxt2=v2[ptr2];
		
		//int val=counter-root->query(in[nxt],out[nxt])-root->query(in[nxt2],out[nxt2]);
		//show(val,val);
		int hold=dp[0][index]-nxt-nxt2+dp[0][a]+dp[0][b]+it.second;
		hold+=root->query(in[a],in[a])+root->query(in[b],in[b]);
		//show(hold2,hold);
		best=max(best,hold);
	}
	
	dp[1][index]=max(dp[0][index],best);
	
	for(auto it:adj[index]){
		if(it==par) continue;
		root->rangeUpd(in[it],out[it],dp[0][index]-dp[1][it]);
	}
	
	//show(index,index);
	//show2(dp[0][index],dp[0][index],dp[1][index],dp[1][index]);
	//for(int y=1;y<=n;y++){
		//cout << root->query(in[y],in[y]) << " ";
	//}
	//cout << "\n";
}

void solve(){
	cin >> n;
	
	int temp,temp2,temp3;
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
	}
	
	dfs(1,-1);
	
	int q;
	cin >> q;
	
	for(int x=0;x<q;x++){
		cin >> temp >> temp2 >> temp3;
		int hold=lca(temp,temp2);
		if(d[temp]>d[temp2]) swap(temp,temp2);
		if(temp==hold){
			storage[temp].push_back({temp2,temp3});
		}
		else{
			storage2[hold].push_back({{temp,temp2},temp3});
		}
	}
	
	root=new node(0,n+5);
	dfs2(1,-1);
	
	
	cout << dp[1][1];
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=1;	
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

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