Submission #114024

#	Time	Username	Problem	Language	Result	Execution time	Memory
114024		Diuven	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	412 ms	39036 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, A;
	void _upt(int p, int x){
		for(; p<=n; p+=p&(-p)) T[p]+=x;
	}
	int _sum(int p){
		int res=0;
		for(; p>0; p-=p&(-p)) res += T[p];
		return res;
	}
  public:
	Seg_t(int sz): n(sz), T(n+1), A(n) {}
    Seg_t(): Seg_t(0) {}
	void upt(int p, int x){ _upt(p+1,x-A[p]), A[p]=x; }
	int sum(int l, int r){ return _sum(r+1) - _sum(l); }
	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){
		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];
		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