| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 42671 | funcsr | Election Campaign (JOI15_election_campaign) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<17)
#define pb push_back
#define _1 first
#define _2 second
struct HLDecomposition {
int N;
vector<vector<int> > G;
vector<int> head, par, next, tid;
HLDecomposition(int N) : N(N), G(N), head(N, -1), par(N, -1), next(N, -1), tid(N, -1) {}
void add_edge(int x, int y) {
G[x].pb(y), G[y].pb(x);
}
int dfs(int x, int p) {
par[x] = p;
int s = 1, mc = 0;
for (int t : G[x]) if (t != p) {
int w = dfs(t, x);
if (w > mc) mc = w, next[x] = t;
s += w;
}
return s;
}
void build() {
assert(dfs(0, -1) == N);
queue<int> q;
int k = 0;
q.push(0);
while (!q.empty()) {
int h = q.front(); q.pop();
for (int v=h; v!=-1; v=next[v]) tid[v] = k++, head[v] = h;
for (int v=h; v!=-1; v=next[v]) for (int t : G[v]) if (tid[t] == -1) q.push(t);
}
assert(k == N);
}
int lca(int u, int v) {
if (tid[u] < tid[v]) swap(u, v);
if (head[u] == head[v]) return v;
return lca(par[head[u]], v);
}
void for_each(int u, int v, function<void(int, int)> f) {
if (tid[u] < tid[v]) swap(u, v);
if (head[u] == head[v]) return f(tid[v], tid[u]);
f(tid[head[u]], tid[u]);
return for_each(par[head[u]], v, f);
}
};
struct BIT {
int n;
vector<int> xs;
BIT(int n) : n(n), xs(n+1, 0) {}
void add(int i, int v) {
for (int x=i+1; x<=n; x+=x&-x) xs[x] += v;
}
int sum(int i) {
int s = 0;
for (int x=i+1; x>0; x-=x&-x) s += xs[x];
return s;
}
int sum(int l, int r) {
if (l > r) return 0;
return sum(r) - sum(l-1);
}
};
int N, M;
int A[100000], B[100000], C[100000];
HLDecomposition hld(0);
BIT bit(0);
vector<int> G[100000];
vector<int> Q[100000];
int dp[100000];
void dfs(int x, int p) {
int sum = 0;
for (int t : G[x]) if (t != p) {
dfs(t, x);
sum += dp[t];
}
dp[x] = sum;
for (int id : Q[x]) {
int u = A[id], v = B[id], w = C[id]+sum;
hld.for_each(u, v, [&](int l, int r) { w += bit.sum(l, r); });
dp[x] = max(dp[x], w);
}
bit.add(hld.tid[x], sum-dp[x]);
}
int main() {
cin >> N;
hld = HLDecomposition(N);
bit = BIT(N);
rep(i, N-1) {
int u, v;
cin >> u >> v;
u--, v--;
G[u].pb(v);
G[v].pb(u);
hld.add_edge(u, v);
}
hld.build();
cin >> M;
rep(i, M) {
cin >> A[i] >> B[i] >> C[i];
A[i]--, B[i]--;
Q[hld.lca(A[i], B[i])].pb(i);
}
dfs(0, -1);
cout << dp[0] << "\n";
return 0;
}