#include <bits/stdc++.h>
using namespace std;
struct query {
int a, b, c;
};
const int N = 1e5;
vector<int> adj[N];
long long subtree[N], dp[N];
vector<query> q[N];
bool check[N];
int parent[N];
int n, m;
vector<int> euler, depth;
int first[N], last[N];
int c = 0;
int sparse[N * 2][18];
long long t[N * 8];
void dfs(int v, int p = -1, int d = 0) {
first[v] = c++;
parent[v] = p;
euler.push_back(v);
depth.push_back(d);
for (int i : adj[v]) {
if (i != p) {
dfs(i, v, d + 1);
euler.push_back(v);
depth.push_back(d);
c++;
}
}
last[v] = c - 1;
}
int merge(int a, int b) {
return depth[a] < depth[b] ? a : b;
}
void build_sparse() {
for (int i = 0; i < euler.size(); i++)
sparse[i][0] = i;
for (int i = 1; i <= log2(n); i++) {
for (int j = 0; j < euler.size() && j - 1 + (1 << i) < euler.size(); j++)
sparse[j][i] = merge(sparse[j][i - 1], sparse[j + (1 << (i - 1))][i - 1]);
}
}
int query_lca(int u, int v) {
if (u == v) return u;
int f1 = min(first[u], first[v]), f2 = max(first[v], first[u]), diff = f2 - f1;
int dx = log2(diff);
return euler[merge(sparse[f1][dx], sparse[f2 + 1 - (1 << dx)][dx])];
}
bool cmp(query u, query v) {
int lca1 = query_lca(u.a, u.b), lca2 = query_lca(v.a, v.b);
if (depth[first[lca1]] == depth[first[lca2]])
return lca1 < lca2;
return depth[first[lca1]] < depth[first[lca2]];
}
long long query_tree(int v, int l, int r, int tl, int tr) {
if (tl > tr)
return 0;
else if (l == tl && r == tr)
return t[v];
int mid = (l + r) / 2;
return query_tree(v * 2, l, mid, tl, min(mid, tr)) + query_tree(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr);
}
void update(int v, int l, int r, int tl, long long val) {
if (l == r && l == tl) {
t[v] = val;
return;
}
int mid = (l + r) / 2;
if (tl <= mid)
update(v * 2, l, mid, tl, val);
else
update(v * 2 + 1, mid + 1, r, tl, val);
t[v] = t[v * 2] + t[v * 2 + 1];
}
long long calc(int v, int p) {
if (check[v])
return dp[v];
for (int i : adj[v]) {
if (i != p)
subtree[v] += calc(i, v);
}
dp[v] = subtree[v];
check[v] = true;
return dp[v];
}
void solve(int v, int p = -1) {
for (int i : adj[v]) {
if (i != p) {
solve(i, v);
subtree[v] += dp[i];
dp[v] += dp[i];
}
}
for (auto i : q[v]) {
/*long long sum = query_tree(1, 0, euler.size() - 1, first[v], first[i.a]) + query_tree(1, 0, euler.size() - 1, first[v], first[i.b]) + subtree[v] + i.c;
dp[v] = max(dp[v], sum);*/
dp[v] = max(dp[v], subtree[v] + query_tree(1, 0, euler.size() - 1, first[v], first[i.a]) + i.c) + query_tree(1, 0, euler.size() - 1, first[v], first[i.b]);
}
update(1, 0, euler.size() - 1, first[v], subtree[v] - dp[v]);
if (v != 0)
update(1, 0, euler.size() - 1, last[v] + 1, dp[v] - subtree[v]);
}
long long solve(query u) {
int lca = query_lca(u.a, u.b);
if (!check[lca]) {
calc(lca, parent[lca]);
}
long long sum = query_tree(1, 0, euler.size() - 1, first[lca], first[u.a]) + query_tree(1, 0, euler.size() - 1, first[lca], first[u.b]) + 2 * (dp[lca] - subtree[lca]) + subtree[lca] + u.c;
if (sum > dp[lca]) {
dp[lca] = sum;
update(1, 0, euler.size() - 1, first[lca], subtree[lca] - dp[lca]);
if (lca != 0)
update(1, 0, euler.size() - 1, last[lca] + 1, dp[lca] - subtree[lca]);
}
assert(sum >= 0);
return sum;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
x--, y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(0);
build_sparse();
cin >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
q[query_lca(a, b)].push_back({a, b, c});
}
// for (int i = 0; i < m; i++) cout << query_lca(q[i].a, q[i].b) << endl;
solve(0);
cout << *max_element(dp, dp + n);
}
Compilation message
election_campaign.cpp: In function 'void build_sparse()':
election_campaign.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < euler.size(); i++)
~~^~~~~~~~~~~~~~
election_campaign.cpp:50:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < euler.size() && j - 1 + (1 << i) < euler.size(); j++)
~~^~~~~~~~~~~~~~
election_campaign.cpp:50:62: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < euler.size() && j - 1 + (1 << i) < euler.size(); j++)
~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5368 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
295 ms |
32736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5368 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5368 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
