Submission #1167936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167936		_rain_	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	89 ms	36312 KiB

election_campaign

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

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

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]=max(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 max(Get(lef(id),l,m,u,v),Get(rig(id),m+1,r,u,v));
		}
};
IT tree;


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];
}

int Find_vert(int u,int dep){
	if (dep<0) return -1;
	for(int i=0;i<=MAXLOG;++i) {
		if ((dep>>i)&1) u=par[u][i];
	}
	return u;
}

const LL INF=(LL)1e16;
LL f[N+2],mx[N+2];

void calc(int u,int p){
	for(auto&v:ke[u]){
		if (v==p) continue;
		calc(v,u);
		mx[u]+=f[v];
		f[u]+=f[v];
	}
	LL tot=f[u];
	for(auto&x:query[u]){
		LL sum=tot;
		if (x.x1==x.y1){
			sum=sum-f[x.x1]+mx[x.x2]+x.cost;
			f[u]=max(f[u],sum);
		}
		else {
			sum=sum-f[x.x1]-f[x.y1]+mx[x.y2]+mx[x.x2]+x.cost;
			f[u]=max(f[u],sum);
		}
	}
	
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
//	freopen("txt.inp","r",stdin);
	
	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);
		int u1=Find_vert(u,h[u]-h[lca]-1);
		int v1=Find_vert(v,h[v]-h[lca]-1);
		if (u1==-1) u1=v1; else if (v1==-1) v1=u1;
		int u2=u,v2=v;
		if (u2==lca) u2=v; else if (v2==lca) v2=u;
		assert(u1!=-1 && v1!=-1);
//		cout<<u1<<' '<<v1<<' '<<u2<<' '<<v2<<' '<<lca<<'\n';
		query[lca].push_back({u1,v1,u2,v2,c});		
	}
	calc(1,0);
	cout<<f[1];
}

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