Submission #114023

#	Time	Username	Problem	Language	Result	Execution time	Memory
114023		Diuven	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	458 ms	45688 KiB

election_campaign

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

const int MAX = 1e5+10;
const int LG = 18;

int n, de[MAX], pa[LG][MAX], su[MAX], dn[MAX];
vector<int> G[MAX];

void dfs1(int v, int p, int d=1){
	de[v] = d, su[v] = 1;
	for(int x:G[v]){
		if(x==p) continue;
		pa[0][x] = v;
		for(int i=1; i<LG; i++) pa[i][x] = pa[i-1][pa[i-1][x]];
		dfs1(x,v,d+1); su[v]+=su[x];
		if(su[dn[v]]<su[x]) dn[v]=x;
	}
}

int lca(int u, int v){
	if(de[u]<de[v]) swap(u,v);
	for(int i=LG-1; i>=0; i--) if(de[u]-(1<<i)>=de[v]) u = pa[i][u];
	if(u==v) return u;
	for(int i=LG-1; i>=0; i--) if(pa[i][u]!=pa[i][v]) u = pa[i][u], v = pa[i][v];
	return pa[0][u];
}

class Seg_t{
	int n; vector<int> T; // sum
	void upt(int v, int s, int e, int p, int x){
		if(p<s || e<p) return;
		if(s==e){ T[v]=x; return; }
		upt(v*2, s, (s+e)/2, p, x); upt(v*2+1, (s+e)/2+1, e, p, x);
		T[v] = T[v*2] + T[v*2+1];
	}
	int sum(int v, int s, int e, int l, int r){
		if(e<l || r<s) return 0;
		if(l<=s && e<=r) return T[v];
		return sum(v*2,s,(s+e)/2,l,r) + sum(v*2+1,(s+e)/2+1,e,l,r);
	}
  public:
	Seg_t(int sz): n(sz) { // [0, n)
		int k=1; while(k<sz) k<<=1;
		T.resize(k<<1, 0);
	}
    Seg_t(): Seg_t(0) {}
	void upt(int p, int x){ upt(1,0,n-1,p,x); }
	int sum(int l, int r){ return sum(1,0,n-1,l,r); }
	int val(int p){ return sum(p,p); }
};

class HLD_t{
	Seg_t Seg[MAX]; int rt[MAX], sz[MAX];
	void dfs0(int v, int p, int c){
		rt[v] = c; sz[c]++;
		for(int x:G[v]) if(x!=p)
			dfs0(x, v, (x==dn[v] ? c : x));
	}
	int sum_u(int x, int v){ // [x,v]
		int res = 0;
		for(int t, r; de[x]>=de[v]; x=pa[0][t]){
			r = rt[x], t = (de[r]<de[v] ? v : r);
			res += Seg[r].sum(de[t]-de[r], de[x]-de[r]);
		}
		return res;
	}
	int val(int v){ return Seg[rt[v]].val(de[v]-de[rt[v]]); }
  public:
    void init(){
		dfs0(1,0,1);
		for(int i=1; i<=n; i++) Seg[i] = Seg_t(sz[i]);
	}
	void upt(int v, int x){
		Seg[rt[v]].upt(de[v]-de[rt[v]], x);
	}
	int sum_p(int x, int y, int p){ return sum_u(x,p) + sum_u(y,p) - val(p); }
} HLD;

vector<int> plan[MAX];
int m, X[MAX], Y[MAX], C[MAX];

int D[MAX], S[MAX];

void dfs2(int v, int p){
	for(int x:G[v]){
		if(x==p) continue;
		dfs2(x,v); S[v]+=D[x];
	}
	D[v] = S[v]; HLD.upt(v, S[v]);

	for(int idx:plan[v]){
		int x=X[idx], y=Y[idx], c=C[idx];
		// 이걸 쓰는 경우: now = c + sum(S[x...y]) - sum(D[x...v)) - sum(D[y...v))
		// (let D[v]=0) now = c + sum(S[x...y]) - sum(D[x...y])
		int now = c + HLD.sum_p(x,y,v);
		D[v] = max(now, D[v]);
	}
	HLD.upt(v, S[v]-D[v]);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n;
	for(int i=1; i<n; i++){
		int u,v; cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1,0);

	HLD.init();

	cin>>m;
	for(int i=1; i<=m; i++){
		cin>>X[i]>>Y[i]>>C[i];
		plan[lca(X[i], Y[i])].push_back(i);
	}

	dfs2(1,0);

	cout<<D[1]<<'\n';

	return 0;
}

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