#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ <<" "<<
const ll MAXN = 1e5+5;
const ll INF = 1e18;
vector<ll> adjlist[MAXN];
bool visited[MAXN];
//lca
ll parent[18][MAXN], depth[MAXN];
ll n;
//hld
ll stsize[MAXN], preorder[MAXN], head[MAXN], id;
void hld_sz(ll u, ll par){
stsize[u] = 1;
for (auto &v : adjlist[u]){
if (v != par) {
hld_sz(v, u);
stsize[u] += stsize[v];
if (adjlist[u][0] == par || stsize[v] > stsize[adjlist[u][0]]) swap(v, adjlist[u][0]);
}
}
return;
}
void hld(ll u, ll par){
preorder[u] = ++id;
if (u == par) head[u] = u;
for (auto v : adjlist[u]){
if (v != par){
head[v] = (v == adjlist[u][0]) ? head[u] : v;
hld(v, u);
}
}
return;
}
void dfs(ll u, ll par, ll dep){
visited[u] = 1;
depth[u] = dep;
parent[0][u] = par;
for (auto v : adjlist[u]){
if (!visited[v]) dfs(v, u, dep+1);
}
return;
}
void lcainit(){
for (int power=1; power<18; power++) for (int i=1; i<=n; i++){
parent[power][i] = parent[power-1][parent[power-1][i]];
}
return;
}
ll lca(ll a, ll b){
if (depth[a] > depth[b]) swap(a,b);
ll diff = depth[b] - depth[a];
ll power = 0;
while (diff){
if (diff%2) b = parent[power][b];
diff>>=1;
power++;
}
if (a == b) return a;
for (int i=17; i>=0; i--){
if (parent[i][a] != parent[i][b]){
a = parent[i][a];
b = parent[i][b];
}
}
return parent[0][a];
}
ll nodesum[MAXN], childsum[MAXN];
void upd(ll x, ll val, ll type){
if (type) {
for (int i=x; i<=n; i+=i&(-i)) nodesum[i] += val;
} else {
for (int i=x; i<=n; i+=i&(-i)) childsum[i] += val;
}
return;
}
ll query(ll a, ll b, ll type){
ll resa=0, resb=0;
if (type) {
for (int i=--a; i; i-=i&(-i)) resa += nodesum[i];
for (int i=b; i; i-=i&(-i)) resb += nodesum[i];
} else {
for (int i=--a; i; i-=i&(-i)) resa += childsum[i];
for (int i=b; i; i-=i&(-i)) resb += childsum[i];
}
return resb-resa;
}
ll dp[MAXN];
bool visit[MAXN];
vector<tuple<ll,ll,ll> > lcas[MAXN];
void solve(ll u){
visit[u] = 1;
for (auto v : adjlist[u]){
if (visit[v]) continue;
solve(v);
dp[u] += dp[v];
}
for (auto paths : lcas[u]){
ll x, y, val;
ll nsum = 0, csum = 0;
tie(x, y, val) = paths;
// cout << x _ y _ val << "gay ";
while (true){
if (head[x] == head[y]){
if (preorder[x] > preorder[y]) swap(x, y);
nsum += query(preorder[x], preorder[y], 1);
csum += query(preorder[x], preorder[y], 0);
break;
} else {
if (depth[head[x]] >= depth[head[y]]) {
nsum += query(preorder[head[x]], preorder[x], 1);
csum += query(preorder[head[x]], preorder[x], 0);
x = parent[0][head[x]];
} else {
nsum += query(preorder[head[y]], preorder[y], 1);
csum += query(preorder[head[y]], preorder[y], 0);
y = parent[0][head[y]];
}
}
}
// cout << csum _ nsum _ val << "vals ";
ll newval = csum - nsum + val;
dp[u] = max(dp[u], newval);
}
upd(preorder[u], dp[u], 1);
upd(preorder[parent[0][u]], dp[u], 0);
// cout << u _ dp[u] << '\n';
return;
}
int main(){
cin >> n;
for (int i=1; i<n; i++){
ll a, b;
cin >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
dfs(1,1,0);
lcainit();
hld_sz(1,1);
hld(1,1);
ll q;
cin >> q;
while (q--) {
ll a, b, c;
cin >> a >> b >> c;
lcas[lca(a,b)].emplace_back(a,b,c);
}
solve(1);
cout << dp[1];
// for (int i=1; i<11; i++) cout << stsize[i] _ preorder[i] _ head[i] << '\n';
// cout << lca(2, 7) _ lca(3, 5) _ lca(1, 1) _ lca(6, 7);
}
Compilation message
election_campaign.cpp: In function 'void solve(ll)':
election_campaign.cpp:112:5: error: reference to 'visit' is ambiguous
112 | visit[u] = 1;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
from election_campaign.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1649 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
election_campaign.cpp:108:6: note: 'bool visit [100005]'
108 | bool visit[MAXN];
| ^~~~~
election_campaign.cpp:114:13: error: reference to 'visit' is ambiguous
114 | if (visit[v]) continue;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
from election_campaign.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1649 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
election_campaign.cpp:108:6: note: 'bool visit [100005]'
108 | bool visit[MAXN];
| ^~~~~
