Submission #961127

#	Time	Username	Problem	Language	Result	Execution time	Memory
961127		Pring	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	84 ms	44656 KiB

election_campaign

#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else 
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

#include<cstdio>
inline char readchar(){
	const int S = 1<<16;
	static char buf[S], *p = buf, *q = buf;
	return p == q and (q = (p = buf) + fread(buf, 1, S, stdin)) == buf ? EOF : *p++;
}

inline int R(){
	int ans = 0; char c = readchar();
	while((c < '0' or c > '9') and c != EOF) c = readchar();
	// if(c == '-') minus = true, c = readchar();
	while(c >= '0' and c <= '9') ans = ans * 10 + (c ^ '0'), c = readchar();
	// return minus ? -ans : ans;
	return ans;
}

const int MXN = 100005;
int n, m, a[MXN], b[MXN], c[MXN];
vector<int> lenid[MXN];
int lca[MXN], dfn[MXN];
ll dp[MXN];

struct BIT {
	int n;
	ll val[MXN];
	void init(int _n) {
		n = _n;
		fill(val + 1, val + n + 1, 0);
	}
	void modify(int id, int v) {
		for (; id <= n; id += (id & -id)) val[id] += v;
	}
	ll query(int id) {
		ll ans = 0;
		for (; id > 0; id -= (id & -id)) ans += val[id];
		return ans;
	}
	ll query(int l, int r) {
		return query(r) - query(l - 1);
	}
} B;

namespace TREE {
	int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], C = 1;
	vector<int> edge[MXN];
	void ADD_EDGE(int x, int y) {
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	void DFS(int id, int par, int dep) {
		p[id] = par;
		d[id] = dep;
		sz[id] = 1;
		son[id] = -1;
		for (auto &i : edge[id]) {
			if (i == par) continue;
			DFS(i, id, dep + 1);
			sz[id] += sz[i];
			if (son[id] == -1 || sz[son[id]] < sz[i]) son[id] = i;
		}
	}
	void HLD(int id, int par, int _t) {
		top[id] = _t;
		dfn[id] = C++;
		if (son[id] != -1) HLD(son[id], id, _t);
		for (auto &i : edge[id]) {
			if (i == par) continue;
			if (i == son[id]) continue;
			HLD(i, id, i);
		}
	}
	void BUILD() {
		DFS(1, 0, 0);
		HLD(1, 0, 1);
	}
	int LCA(int x, int y) {
		while (top[x] != top[y]) {
			if (d[top[x]] < d[top[y]]) swap(x, y);
			x = p[top[x]];
		}
		return (d[x] > d[y] ? y : x);
	}
}

ll JUMP(int rt, int x) {
	using namespace TREE;
	ll ans = 0;
	while (top[x] != top[rt]) {
		ans += B.query(dfn[top[x]], dfn[x]);
		x = p[top[x]];
	}
	return ans + B.query(dfn[rt] + 1, dfn[x]);
}

void DP(int id, int par) {
	ll sum = 0;
	for (auto &i : TREE::edge[id]) {
		if (i == par) continue;
		DP(i, id);
		sum += dp[i];
	}
	dp[id] = sum;
	for (auto &e : lenid[id]) {
		int l = JUMP(id, a[e]), r = JUMP(id, b[e]);
		ll now = sum + c[e] - l - r;
		dp[id] = max(dp[id], now);
	}
	B.modify(dfn[id], dp[id] - sum);
}

void miku() {
	int x, y;
	// cin >> n;
	n = R();
	FOR(i, 1, n) {
		// cin >> x >> y;
		x = R();
		y = R();
		TREE::ADD_EDGE(x, y);
	}
	TREE::BUILD();
	// cin >> m;
	m = R();
	FOR(i, 0, m) {
		// cin >> a[i] >> b[i] >> c[i];
		a[i] = R();
		b[i] = R();
		c[i] = R();
		lca[i] = TREE::LCA(a[i], b[i]);
		lenid[lca[i]].push_back(i);
	}
	B.init(n);
	DP(1, 0);
	// cout << dp[1] << '\n';
	printf("%lld\n", dp[1]);
}

int32_t main() {
	// cin.tie(0) -> sync_with_stdio(false);
	// cin.exceptions(cin.failbit);
	miku();
	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