Submission #297603

#	Time	Username	Problem	Language	Result	Execution time	Memory
297603		limabeans	Election Campaign (JOI15_election_campaign)	C++17	20 / 100	1056 ms	139356 KiB

election_campaign

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const int LOG = 20;

int n, m;
vector<int> g[maxn];
int dep[maxn];
int par[maxn][LOG+1];
vector<int> leaves[maxn];
ll dp0[maxn]; // no path goes direct thru me
ll dp1[maxn]; // path goes directly thru me
vector<ll> dp[maxn]; // no path thru me, and no path thru ith leaf


void gen(int at, int p) {
    for (int j=1; j<LOG; j++) {
	par[at][j] = par[par[at][j-1]][j-1];
    }
    for (int to: g[at]) {
	if (to==p) continue;
	leaves[at].push_back(to);
	par[to][0]=at;
	dep[to]=1+dep[at];
	gen(to,at);
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x,y);
    int dx=dep[x]-dep[y];
    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    x=par[x][j];
	}
    }
    if (x==y) return x;

    for (int j=LOG-1; j>=0; j--) {
	if (par[x][j] != par[y][j]) {
	    x=par[x][j];
	    y=par[y][j];
	}
    }

    return par[x][0];    
}

int a[maxn], b[maxn];
ll c[maxn];
vector<int> qu[maxn];


void procQuery(int i) {
    int from = a[i];
    int to = b[i];

    int mid = lca(from, to);
    qu[mid].push_back(i);
}


void dfs(int at) {

    vector<ll> pre;
    for (int to: leaves[at]) {
	dfs(to);
	ll tmp = max(dp0[to], dp1[to]);
	pre.push_back(tmp);
	dp0[at] += tmp;
    }
    int lcount = leaves[at].size();
    for (int i=1; i<lcount; i++) {
	pre[i] += pre[i-1];
    }

    auto qry = [&](int l, int r) {
	if (l>r) return 0ll;
	return pre[r] - (l>0 ? pre[l-1] : 0ll);
    };
    
    dp[at].resize(lcount);

    // ith leaf is banned
    for (int i=0; i<lcount; i++) {
	dp[at][i] = qry(0,i-1) + qry(i+1, lcount-1);
    }


    for (int qi: qu[at]) {
	vector<vector<int>> paths;
	// get paths a->at and at<-b
	for (int nd: {a[qi],b[qi]}) {
	    if (nd==at) continue;
	    vector<int> path = {nd};
	    while (par[nd][0] != at) {
		nd=par[nd][0];
		path.push_back(nd);
	    }
	    reverse(path.begin(), path.end());
	    paths.push_back(path);
	}
	ll cur = c[qi];

	assert(int(paths.size()) <= 2);
	
	for (int to: leaves[at]) {
	    int id=-1;
	    for (int j=0; j<int(paths.size()); j++) {
		if (paths[j].front() == to) {
		    id = j;
		}
	    }

	    // at->to->...a
	    if (~id) {
		auto &p = paths[id];
		int plen = p.size();
		for (int j=0; j<plen; j++) {
		    if (j==plen-1) {
			int end = p[j];
			cur += dp0[end];
		    } else {
			int nid=0;
			while (leaves[p[j]][nid] != p[j+1]) nid++;
			cur += dp[p[j]][nid];
		    }
		}
	    } else {
		cur += max(dp0[to],dp1[to]);
	    }
	}

	dp1[at] = max(dp1[at], cur);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

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

    gen(0,0);

    cin>>m;
    for (int i=0; i<m; i++) {
	cin>>a[i]>>b[i]>>c[i];
	--a[i];
	--b[i];
	procQuery(i);
    }


    dfs(0);
    ll res = max(dp0[0], dp1[0]);
    cout<<res<<endl;    
    return 0;
}

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