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"
using namespace std;
const int maxn = 1e5 + 5;
const int lg = 18;
int n, a[maxn];
vector<int> g[maxn];
int pos[maxn], cur_pos, head[maxn];
int up[maxn][lg + 1];
int sz[maxn], par[maxn];
int h[maxn];
int eu[maxn], ev[maxn];
int rev[maxn];
pair<int, int> tree[maxn * 4];
int lazy[maxn * 4];
pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
return {max(a.first, b.first), min(a.second, b.second)};
}
struct fenwick_tree {
#define gb(x) (x) & (-x)
int n;
vector<long long> bit;
fenwick_tree() {}
fenwick_tree(int n) : n(n), bit(n + 5, 0) {}
void update(int x, long long val) {
for(int i = x; i <= n; i += gb(i)) bit[i] += val;
}
long long get(int x) {
int ans = 0;
for(int i = x; i > 0; i -= gb(i)) ans += bit[i];
return ans;
}
} fen;
struct segment_tree {
int n;
segment_tree() {}
segment_tree(int n) : n(n) {
for(int i = 1; i <= n * 4; ++i) {
tree[i] = {0, 2e9};
}
}
void build(int ind, int l, int r) {
if(l == r) {
tree[ind] = {a[rev[l]], a[rev[l]]};
return;
}
int mid = (l + r) / 2;
build(ind * 2, l, mid);
build(ind * 2 + 1, mid + 1, r);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
}
void down(int ind, int l, int r) {
tree[ind].first = tree[ind].second = lazy[ind];
if(l != r) {
lazy[ind * 2] = lazy[ind * 2 + 1] = lazy[ind];
}
lazy[ind] = 0;
}
void update(int ind, int l, int r, int x, int y, int val) {
if(lazy[ind]) down(ind, l, r);
if(l > y || r < x) return;
if(x <= l and r <= y) {
lazy[ind] = val;
down(ind, l, r);
return;
}
int mid = (l + r) / 2;
update(ind * 2, l, mid, x, y, val);
update(ind * 2 + 1, mid + 1, r, x, y, val);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
}
pair<int, int> get(int ind, int l, int r, int x, int y) {
if(lazy[ind]) down(ind, l, r);
if(l > y || r < x) return {0, 2e9};
if(x <= l and r <= y) return tree[ind];
int mid = (l + r) / 2;
return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y);
}
void update(int x, int y, int val) {
update(1, 1, n, x, y, val);
}
pair<int, int> get(int x, int y) {
return get(1, 1, n, x, y);
}
} st;
void pre_dfs(int u, int prev) {
sz[u] = 1;
for(auto v:g[u]) {
if(v == prev) continue;
par[v] = u;
h[v] = h[u] + 1;
up[v][0] = u;
pre_dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u, int prev) {
if(!head[u]) {
head[u] = u;
}
pos[u] = ++cur_pos;
rev[cur_pos] = u;
int big_child = -1;
for(auto v:g[u]) {
if(v == prev) continue;
if(big_child == -1 || sz[big_child] < sz[v]) big_child = v;
}
if(big_child != -1) {
head[big_child] = head[u];
hld(big_child, u);
}
for(auto v:g[u]) {
if(v == prev || v == big_child) continue;
hld(v, u);
}
}
void update(int u, int v, int val) {
while(head[u] != head[v]) {
if(h[u] > h[v]) swap(u, v);
st.update(pos[head[v]], pos[v], val);
v = par[head[v]];
}
if(h[u] > h[v]) swap(u, v);
st.update(pos[u], pos[v], val);
}
pair<int, int> get(int u, int v) {
pair<int, int> ans = {0, 2e9};
while(head[u] != head[v]) {
if(h[u] > h[v]) swap(u, v);
ans = ans + st.get(pos[head[v]], pos[v]);
v = par[head[v]];
}
if(h[u] > h[v]) swap(u, v);
ans = ans + st.get(pos[u], pos[v]);
return ans;
}
void solve() {
cin >> n;
vector<int> cpr;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
cpr.push_back(a[i]);
}
sort(cpr.begin(), cpr.end());
cpr.erase(unique(cpr.begin(), cpr.end()), cpr.end());
for(int i = 1; i <= n; ++i) {
a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin() + 1;
}
fen = fenwick_tree((int)cpr.size() + 5);
for(int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
eu[i] = u, ev[i] = v;
g[u].push_back(v);
// g[v].push_back(u);
}
pre_dfs(1, 0);
for(int i = 1; i <= lg; ++i) {
for(int u = 1; u <= n; ++u) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
}
hld(1, 0);
st = segment_tree(n);
st.build(1, 1, n);
for(int t = 1; t < n; ++t) {
int u = eu[t], v = ev[t];
vector<pair<int, int>> vec;
int ver = u;
while(ver) {
vec.push_back({st.get(pos[ver], pos[ver]).first, 1});
for(int i = lg; i >= 0; --i) {
if(!up[ver][i]) continue;
int nxt = up[ver][i];
pair<int, int> dit = get(ver, nxt);
if(dit.first == dit.second) {
ver = nxt;
vec.back().second += (1 << i);
}
}
ver = par[ver];
}
long long ans = 0;
for(int i = 0; i < (int)vec.size(); ++i) {
ans += vec[i].second * fen.get(vec[i].first - 1);
fen.update(vec[i].first, vec[i].second);
}
for(auto i:vec) {
fen.update(i.first, -i.second);
}
cout << ans << '\n';
update(1, u, st.get(pos[v], pos[v]).first);
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |