Submission #264184

#	Time	Username	Problem	Language	Result	Execution time	Memory
264184		ruler	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	267 ms	32152 KiB

election_campaign

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

#define endl '\n'
#define ends ' '
#define endt '\t'
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////
 
const int N = 1e5 + 5, LOG = 17;

int S[N], F[N], H[N], P[LOG][N], ts;
int DP[N][3],  FEN[N];
vector<int> G[N];
int A[N], B[N], C[N];
vector<int> Q[N];

void Add(int p, int x) { for (p++; p < N; p += p & -p) FEN[p] += x; }
int Get(int p) {
	int res = 0;
	for (p++; p > 0; p -= p & -p) res += FEN[p];
	return res;
}
void DFSH(int v, int p = 0) {
	S[v] = ts++, P[0][v] = p;
	for (int i = 1; i < LOG; i++) P[i][v] = P[i - 1][P[i - 1][v]];
	for (int u : G[v]) if (u != p) H[u] = H[v] + 1, DFSH(u, v);
	F[v] = ts;
}
int GetPar(int v, int h) {
	for (int i = 0; i < LOG; i++) if ((h >> i) & 1) v = P[i][v];
	return v;
}
int GetLCA(int v, int u) {
	if (H[v] < H[u]) swap(v, u);
	v = GetPar(v, H[v] - H[u]);
	if (v == u) return v;
	for (int i = LOG - 1; i >= 0; i--) if (P[i][v] != P[i][u])
		v = P[i][v], u = P[i][u];
	return P[0][v];
}
void DFS(int v, int p = 0) {
	for (int u : G[v]) if (u != p) {
		DFS(u, v);
		DP[v][0] += DP[u][2];
	}
	for (int u : G[v]) if (u != p) {
		Add(S[u], DP[v][0] - DP[u][2]);
		Add(F[u], DP[u][2] - DP[v][0]);
	}
	for (int q : Q[v]) {
		int a = A[q], b = B[q], c = C[q];
		DP[v][1] = max(DP[v][1], c + Get(S[a]) + Get(S[b]) + DP[a][0] + DP[b][0] - DP[v][0]);
	}
	DP[v][2] = max(DP[v][0], DP[v][1]);
}

int main() {
 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n; cin >> n;
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	DFSH(1);
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> A[i] >> B[i] >> C[i];
		Q[GetLCA(A[i], B[i])].push_back(i);
	}
	DFS(1);
	cout << DP[1][2] << endl;

	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