#include "bits/stdc++.h"
#define endl '\n'
constexpr int maxn = 1e5+5;
constexpr int mod = 1e9+7;
using namespace std;
using lint = long long;
constexpr lint maxk = 1e9;
constexpr lint inf = 1e18;
using pll = pair<lint, lint>;
int n;
lint val[maxn];
vector<int> adj[maxn];
int m, h;
int tin[maxn], tout[maxn], b[2 * maxn], p[maxn];
pll t[4 * maxn];
int lz[2 * maxn];
bool vis[maxn];
lint ans;
void dfs(int u) {
b[m] = u;
tin[u] = m;
m++;
for(int v : adj[u])
if(v != p[u]) {
p[v] = u;
dfs(v);
}
b[m] = u;
tout[u] = m;
m++;
}
void build() {
h = 8 * sizeof(int) - __builtin_clz(m);
for(int i = 0; i < m; i++) {
t[m + i].first = val[b[i]];
t[m + i].second = b[i];
}
for(int i = m - 1; i >= 1; i--) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
lz[i] = 1;
}
}
void apply(int u, lint val) {
t[u].first *= val;
if(u < m)
lz[u] *= val;
}
void fixup(int u) {
for(u >>= 1; u; u >>= 1) {
t[u] = max(t[u << 1], t[u << 1 | 1]);
t[u].first *= lz[u];
}
}
void push(int u) {
for(int k = h; k > 0; k--) {
int s = u >> k;
if(!s)
continue;
apply(s << 1, lz[s]);
apply(s << 1 | 1, lz[s]);
lz[s] = 1;
}
}
void update(int l, int r, lint k) {
l += m;
r += m;
int l0 = l, r0 = r;
for(; l <= r; l >>= 1, r >>= 1) {
if(l & 1)
apply(l++, k);
if(r + 1 & 1)
apply(r--, k);
}
fixup(l0);
fixup(r0);
}
pll query(int l, int r) {
pll ret = {-inf, 0};
if(l > r)
return ret;
l += m;
r += m;
push(l);
push(r);
for(; l <= r; l >>= 1, r >>= 1) {
if(l & 1)
ret = max(ret, t[l++]);
if(r + 1 & 1)
ret = max(ret, t[r--]);
}
return ret;
}
void solve(int u) {
vis[u] = true;
if(adj[u].size() <= 1) {
update(tin[u], tout[u], 0);
return;
}
while(true) {
lint x, mx;
tie(x, mx) = query(tin[u], tout[u]);
if(u == mx) {
for(int v : adj[u]) {
if(vis[v] || p[u] == v)
continue;
ans += x + query(tin[v], tout[v]).first;
solve(v);
update(tin[v], tout[v], 0);
}
update(tin[u], tout[u], 0);
return;
}
else {
lint q1 = query(tin[u], tin[mx] - 1).first;
lint q2 = query(tout[mx] + 1, tout[u]).first;
lint comp2 = max(q1, q2);
ans += comp2 + x;
solve(mx);
update(tin[mx], tout[mx], 0);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> val[i];
if(n == 1) {
cout << 0 << endl;
return 0;
}
if(n == 2) {
cout << val[1] + val[2] << endl;
return 0;
}
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int root = -1;
for(int i = 1; i <= n; i++)
if(adj[i].size() > 1) {
root = i;
break;
}
dfs(root);
build();
solve(root);
cout << ans << endl;
}
Compilation message
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from sjekira.cpp:1:
/usr/include/c++/10/tuple: In instantiation of 'constexpr const size_t std::tuple_size_v<int>':
/usr/include/c++/10/tuple:1733:24: required from 'constexpr decltype(auto) std::apply(_Fn&&, _Tuple&&) [with _Fn = int; _Tuple = int&]'
sjekira.cpp:65:28: required from here
/usr/include/c++/10/tuple:1251:61: error: incomplete type 'std::tuple_size<int>' used in nested name specifier
1251 | inline constexpr size_t tuple_size_v = tuple_size<_Tp>::value;
| ^~~~~
sjekira.cpp: In function 'void update(int, int, lint)':
sjekira.cpp:78:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
78 | if(r + 1 & 1)
| ~~^~~
sjekira.cpp: In function 'pll query(int, int)':
sjekira.cpp:96:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
96 | if(r + 1 & 1)
| ~~^~~
