Submission #683225

#	Time	Username	Problem	Language	Result	Execution time	Memory
683225		NK_	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	179 ms	33608 KiB

election_campaign

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

struct BIT {
	vector<int> data; int N;
	void init(int n) { N = n; data = vector<int>(N, 0); }
	void add(int p, int x) { for(++p;p<=N;p+=p&-p) data[p-1] += x; }
	int sum(int l, int r) { return sum(r+1)-sum(l); }
	int sum(int r) { int s = 0; for(;r;r-=r&-r) s += data[r-1]; return s; }
};

const int LG = 20;
const int nax = 1e5+5;

int up[nax][LG], dep[nax];
int st[nax], en[nax];
vector<int> adj[nax];
vector<int> T[nax];
int U[nax], V[nax], W[nax];
int dp[nax];
BIT DP, CHD;

int t = 0;
void gen(int u = 0, int p = -1) {
	st[u] = t++;

	up[u][0] = (p == -1 ? u : p); dep[u] = (p == -1 ? 0 : dep[p]+1);
	for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

	for(auto v : adj[u]) if (v != p) gen(v, u);	

	en[u] = t++;
}

int jmp(int u, int d) {
	for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
	return u;
}

int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	a = jmp(a, dep[a] - dep[b]);
	if (a == b) return a;

	for(int i = LG - 1; i >= 0; i--) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];

	return up[a][0];
}

void dfs(int u = 0, int p = -1) {
	int chd = 0;
	for(auto v : adj[u]) if (v != p) {
		dfs(v, u);
		chd += dp[v];
	}

	dp[u] = chd;
	CHD.add(st[u], chd); CHD.add(en[u], -chd);

	for(auto i : T[u]) {
		int x = W[i];
		x += CHD.sum(st[u], st[U[i]]) - DP.sum(st[u], st[U[i]]);
		x += CHD.sum(st[u], st[V[i]]) - DP.sum(st[u], st[V[i]]);
		x -= CHD.sum(st[u], st[u]);
		dp[u] = max(dp[u], x);
	}

	DP.add(st[u], dp[u]); DP.add(en[u], -dp[u]);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	gen();

	DP.init(2*N); CHD.init(2*N);

	int Q; cin >> Q;

	for(int i = 0; i < Q; i++) {
		int u, v, w; cin >> u >> v >> w; --u, --v;
		int l = lca(u, v);
		U[i] = u, V[i] = v, W[i] = w;
		T[l].push_back(i);
	}

	dfs();
	
	cout << dp[0] << nl;

    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