Submission #527841

#	Time	Username	Problem	Language	Result	Execution time	Memory
527841		AriaH	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	211 ms	73992 KiB

election_campaign

/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

///int par[LOG][N];

int n, m, ptr, q, H[N], St[N], Fi[N], sub[N], Hv[N], Hd[N], P[N], fir[N], sec[N], cost[N];

struct Fenwick
{
	ll fen[N];
	void add(int i, ll x)
	{
		for(i += 5; i < N; i += i & -i) fen[i] += x;
	}
	ll _ask(int i, ll ret = 0)
	{
		for(i += 5; i; i -= i & -i)
		{
			ret += fen[i];
		}
		return ret;
	}
	ll ask(int l, int r)
	{
		return _ask(r) - _ask(l - 1);
	}
} DP, SUM;

ll dp[N], sum[N];

vector < int > G[N], Vec[N];

void pre(int v)
{
	/*for(int T = 1; T < LOG; T ++)
	{
		par[T][v] = par[T - 1][par[T - 1][v]];
	}
	*/
	sub[v] = 1;
	for(auto u : G[v])
	{
		if(u == P[v]) continue;
		H[u] = H[v] + 1;
		P[u] = v;
		pre(u);
		if(sub[u] > sub[Hv[v]]) Hv[v] = u;
		sub[v] += sub[u];
	}
	///printf("v = %d sub = %d Hv = %d\n", v, sub[v], Hv[v]);
}

void dfs(int v)
{
	St[v] = ++ptr;
	if(Hv[v] > 0)
	{
		Hd[Hv[v]] = Hd[v];
		dfs(Hv[v]);
	}
	for(auto u : G[v])
	{
		if(u == P[v] || u == Hv[v]) continue;
		Hd[u] = u;
		dfs(u);
	}
	Fi[v] = ptr;
}

inline int LCA(int v, int u)
{
	while(Hd[v] != Hd[u])
	{
		if(H[Hd[v]] < H[Hd[u]]) swap(u, v);
		v = P[Hd[v]];
	}
	if(H[v] < H[u]) swap(v, u);
	return u;
}

inline ll G1(int v, int u)
{
	ll ret = 0;
	while(Hd[v] != Hd[u])
	{
		ret -= DP.ask(St[Hd[v]], St[v]);
		ret += SUM.ask(St[Hd[v]], St[v]);
		v = P[Hd[v]];
	}
	ret -= DP.ask(St[u], St[v]);
	ret += SUM.ask(St[u], St[v]);
	return ret;
}

void solve(int v)
{
	for(auto u : G[v])
	{
		if(u == P[v]) continue;
		solve(u);
		sum[v] += dp[u];
	}
	dp[v] = sum[v];
	for(auto id : Vec[v])
	{
		ll now = G1(fir[id], v) + G1(sec[id], v) + sum[v] + cost[id];
		dp[v] = max(dp[v], now);
	}
	SUM.add(St[v], sum[v]);
	DP.add(St[v], dp[v]);
	///printf("v = %d dp = %lld sum = %lld\n", v, dp[v], sum[v]);
}

int main()
{
	fast_io;
	cin >> n;
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	pre(1);
	dfs(Hd[1] = 1);
	cin >> q;
	for(int i = 1; i <= q; i ++)
	{
		cin >> fir[i] >> sec[i] >> cost[i];
		int lca = LCA(fir[i], sec[i]);
		Vec[lca].push_back(i);
		///printf("lca = %d\n", lca);
	}
	solve(1);
	cout << dp[1];
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

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