#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;
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 < n && j - 1 + (1 << i) < n; 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];
}
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;
if (lca != 0)
update(1, 0, euler.size() - 1, first[lca], subtree[lca] - dp[lca]) ,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);
}
cin >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
q.push_back({a, b, c});
}
dfs(0);
build_sparse();
// for (int i = 0; i < m; i++) cout << query_lca(q[i].a, q[i].b) << endl;
sort(q.begin(), q.end(), &cmp);
reverse(q.begin(), q.end());
long long ans = 0;
for (query i : q) {
ans = max(ans, solve(i));
}
cout << ans;
}
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++)
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
382 ms |
28780 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |