| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 486768 | Nimbostratus | Sjekira (COCI20_sjekira) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}