#include "bits/stdc++.h"
#define int long long
#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];
set<pll> s;
int m, h;
int tin[maxn], tout[maxn], b[maxn];
lint t[4 * maxn], lz[2 * maxn];
bool vis[maxn];
lint ans;
void dfs(int u, int p = -1) {
b[m] = u;
tin[u] = m;
m++;
for(int v : adj[u])
if(v != p)
dfs(v, u);
b[m] = u;
tout[u] = m;
m++;
s.insert({val[u], tin[u]});
}
void build() {
h = 8 * sizeof(int) - __builtin_clz(m);
for(int i = 0; i < m; i++)
t[m + i] = val[b[i]];
for(int i = m - 1; i >= 1; i--)
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
void apply(int u, lint val) {
t[u] += 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]) + lz[u];
}
void push(int u) {
for(int k = h; k > 0; k--) {
int p = u >> k;
apply(p << 1, lz[p]);
apply(p << 1 | 1, lz[p]);
lz[p] = 0;
}
}
void update(int l, int r, lint val) {
l += m;
r += m;
int l0 = l, r0 = r;
for(; l <= r; l >>= 1, r >>= 1) {
if(l & 1)
apply(l++, val);
if(r + 1 & 1)
apply(r--, val);
}
fixup(l0);
fixup(r0);
}
lint query(int l, int r) {
if(l > r)
return -inf;
lint ret = -inf;
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)
return;
while(true) {
auto it = s.lower_bound({query(tin[u], tout[u]), tin[u]});
if(it == s.end())
return;
int mx = b[it->second];
s.erase(it);
if(u == mx) {
for(int v : adj[u]) {
if(vis[v])
continue;
ans += val[u] + query(tin[v], tout[v]);
solve(v);
}
return;
}
else {
lint other = max(query(tin[u], tin[mx] - 1), query(tout[mx] + 1, tout[u]));
ans += other + val[mx];
solve(mx);
update(tin[mx], tout[mx], -maxk);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> val[i];
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;
}
if(root == -1) {
cout << val[1] + val[2] << endl;
return 0;
}
dfs(root);
build();
solve(root);
cout << ans << endl;
}
Compilation message
sjekira.cpp: In function 'void update(long long int, long long int, lint)':
sjekira.cpp:70:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
70 | if(r + 1 & 1)
| ~~^~~
sjekira.cpp: In function 'lint query(long long int, long long int)':
sjekira.cpp:88:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
88 | if(r + 1 & 1)
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
38060 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
