#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
//#define int long long
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
vector<int> adj[MAXN];
int n, m;
vector<int> e;
int dep[MAXN];
int par[17][MAXN];
void tour(int node, int prv) {
e.push_back(node);
dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
par[0][node] = prv;
for(int x: adj[node]) {
if(x != prv) {
tour(x, node);
e.push_back(node);
}
}
}
int l[MAXN], r[MAXN];
pair<int, int> st[18][2*MAXN]; // euler tour
int lca_dep(int x, int y) {
int m1 = min(l[x], l[y]);
int m2 = max(r[x], r[y]);
int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
return min(st[k][m1], st[k][m2 - (1<<k) + 1]).first;
}
int lca_idx(int x, int y) {
int m1 = min(l[x], l[y]);
int m2 = max(r[x], r[y]);
int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
return min(st[k][m1], st[k][m2 - (1<<k) + 1]).second;
}
struct plan {
int u, v, cost;
};
vector<plan> v[MAXN];
int dpf(int node, int prv) {
int sum = 0;
unordered_map<int, int> contrib;
for(int x: adj[node]) {
if(x != prv) {
int d = dpf(x, node);
sum += d;
contrib[x] = d;
}
}
int ans = sum;
if(v[node].size()) {
for(plan f: v[node]) {
if(f.u == node || f.v == node) {
int dist = dep[(f.v == node ? f.u : f.v)] - dep[node] - 1;
int cur = (f.u == node ? f.v : f.u);
for(int k=16; k>=0; k--) {
if(dist >= (1 << k)) {
dist -= (1 << k);
cur = par[k][cur];
}
}
ans = max(ans, f.cost + sum - contrib[cur]);
}
else {
int dist = dep[f.u] - dep[node] - 1;
int cur = f.u;
for(int k=16; k>=0; k--) {
if(dist >= (1 << k)) {
dist -= (1 << k);
cur = par[k][cur];
}
}
int dist2 = dep[f.v] - dep[node] - 1;
int cur2 = f.v;
for(int k=16; k>=0; k--) {
if(dist2 >= (1 << k)) {
dist2 -= (1 << k);
cur2 = par[k][cur2];
}
}
ans = max(ans, f.cost + sum - contrib[cur] - contrib[cur2]);
}
}
}
return ans;
}
void solve(int tc) {
cin >> n;
for(int i=1; i<n; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
e.push_back(0);
tour(1, -1);
for(int i=1; i<e.size(); i++) {
if(l[e[i]] == 0) l[e[i]] = i;
r[e[i]] = i;
}
for(int i=1; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
for(int i=1; i<18; i++) {
for(int j=1; j<e.size(); j++) {
st[i][j] = min(st[i-1][j], st[i-1][j + (1<< (i-1))]);
}
}
for(int i=1; i<17; i++) {
for(int j=1; j<=n; j++) {
par[i][j] = par[i-1][par[i-1][j]];
}
}
cin >> m;
for(int i=1; i<=m; i++) {
int q, w, z;
cin >> q >> w >> z;
int j = lca_idx(q, w);
v[j].push_back({q, w, z});
}
cout << dpf(1, -1) << "\n";
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;// cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
election_campaign.cpp: In function 'void solve(int)':
election_campaign.cpp:103:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i=1; i<e.size(); i++) {
| ~^~~~~~~~~
election_campaign.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i=1; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
| ~^~~~~~~~~
election_campaign.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int j=1; j<e.size(); j++) {
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5208 KB |
Output is correct |
2 |
Correct |
3 ms |
5252 KB |
Output is correct |
3 |
Incorrect |
3 ms |
5208 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5200 KB |
Output is correct |
2 |
Incorrect |
3 ms |
5208 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5200 KB |
Output is correct |
2 |
Incorrect |
3 ms |
5208 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
173 ms |
49228 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5208 KB |
Output is correct |
2 |
Correct |
3 ms |
5252 KB |
Output is correct |
3 |
Incorrect |
3 ms |
5208 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5208 KB |
Output is correct |
2 |
Correct |
3 ms |
5252 KB |
Output is correct |
3 |
Incorrect |
3 ms |
5208 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |