#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
const int N = 2e5 + 5;
struct BIT {
vector<int> bit;
int n;
BIT() {}
BIT(int _n) : n(_n) {
bit.resize(n + 3);
}
void update(int id, int val) {
for (int i = id; i <= n; i += (i & -i)) bit[i] += val;
}
int get(int id) {
int res = 0;
for (int i = id; i > 0; i -= (i & -i)) res += bit[i];
return res;
}
} res, total;
int n, m;
struct Data {
int u, v, c;
Data() {}
Data(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
};
vector<int> g[N];
vector<Data> vec[N];
int h[N], st[N], en[N], timedfs, up[N][20];
int f[N];
void pre_dfs(int u, int p) {
st[u] = ++timedfs;
for (int v : g[u]) {
if (v == p) continue;
h[v] = h[u] + 1;
up[v][0] = u;
for (int i = 1; i < 20; i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
pre_dfs(v, u);
}
en[u] = ++timedfs;
}
int lca(int u, int v) {
if (h[u] != h[v]) {
if (h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for (int i = 0; (1 << i) <= k; i++) {
if ((k >> i) & 1) {
u = up[u][i];
}
}
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
void dfs(int u, int p) {
int ans = 0;
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u);
ans += res.get(st[v]);
}
for (auto &cur : vec[u]) {
int tmp = cur.c;
tmp += total.get(st[cur.u]) + total.get(st[cur.v]) + f[u];
tmp -= res.get(st[cur.u]) + res.get(st[cur.v]);
ans = max(ans, tmp);
}
res.update(st[u], ans);
res.update(en[u] + 1, -ans);
f[p] += ans;
total.update(st[u], f[u]);
total.update(en[u] + 1, -f[u]);
}
signed main(){
ios_base::sync_with_stdio(false) ;
cin.tie(0) ; cout.tie(0) ;
if (fopen("INP.INP" ,"r")) {
freopen("INP.INP" ,"r" , stdin) ;
freopen("OUT.OUT" , "w" , stdout) ;
}
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
pre_dfs(1, 0);
cin >> m;
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
int l = lca(u, v);
vec[l].emplace_back(u, v, c);
}
res = BIT(2 * n);
total = BIT(2 * n);
dfs(1, 0);
cout << res.get(st[1]);
}
Compilation message (stderr)
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | freopen("INP.INP" ,"r" , stdin) ;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen("OUT.OUT" , "w" , stdout) ;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |