// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair
//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e5 + 10, LOG = 30;
int n, u[N], v[N], a[N];
int h[N], st[N], fn[N], tim;
int par[N][LOG];
vector<int> adj[N];
void dfs(int x, int p = 0) {
st[x] = tim++;
par[x][0] = p;
for(int i = 1; i < LOG; i++) par[x][i] = par[par[x][i - 1]][i - 1];
h[x] = h[p] + 1;
for(auto j : adj[x]) {
if(j == p) continue;
dfs(j, x);
}
fn[x] = tim;
}
struct node {
int mx, cnt;
node() {
mx = cnt = 0;
}
};
struct Seg {
node x[N << 2];
node merge(node a, node b) {
node res;
res = a;
if(b.mx > a.mx) res = b;
return res;
}
void change(int l, int r, int ind, int val, int timer, int v) {
if(r - l < 2) {
x[v].mx = timer, x[v].cnt = a[val];
return;
}
int mid = (l + r) >> 1;
if(ind < mid) change(l, mid, ind, val, timer, 2 * v);
else change(mid, r, ind, val, timer, 2 * v + 1);
x[v] = merge(x[2 * v], x[2 * v + 1]);
}
node get(int l, int r, int s, int e, int v) {
node res;
if(r <= s || l >= e) return res;
if(l >= s && r <= e) return x[v];
int mid = (l + r) >> 1;
return merge(get(l, mid, s, e, 2 * v), get(mid, r, s, e, 2 * v + 1));
}
} S;
int find(int v) {
node b = S.get(0, n, st[v], fn[v], 1);
for(int i = LOG - 1; i >= 0; i--) {
int p = par[v][i];
if(p == 0) continue;
node a = S.get(0, n, st[p], fn[p], 1);
if(a.mx == b.mx) v = p;
}
return v;
}
struct Fenwick {
int fen[N];
vector<int> his;
Fenwick() {
his.clear();
memset(fen, 0, sizeof(fen));
}
void upd(int ind, int val) {
for(++ind; ind < N; ind += ind & -ind) {
fen[ind] += val;
his.push_back(ind);
}
}
int get(int ind) {
int sum = 0;
for(++ind; ind; ind -= ind & -ind)
sum += fen[ind];
return sum;
}
void clear() {
for(auto j : his) fen[j] = 0;
his.clear();
}
} F;
int main() {
ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);
cin >>n;
for(int i = 1; i <= n; i++) cin >>a[i];
for(int i = 0; i < n - 1; i++) {
cin >>u[i] >>v[i];
adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
}
dfs(1);
S.change(0, n, st[1], 1, 1, 1);
for(int i = 0; i < n - 1; i++) {
int x = u[i], y = v[i];
if(par[x][0] == y) swap(x, y);
ll ans = 0;
while(x) {
int X = find(x);
int cur = h[x] - h[X] + 1;
int val = S.get(0, n, st[x], fn[x], 1).cnt;
ans += 1ll * F.get(val - 1) * cur;
F.upd(val, cur);
x = par[X][0];
}
S.change(0, n, st[y], y, i + 2, 1);
F.clear();
cout<<ans <<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
12336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
12336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
12336 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
