#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
struct node {
node *path_par;
node *p;
node *c[2];
int live;
int cnt;
};
bool side(node *v)
{
return v->p->c[1] == v;
}
void rot(node *v)
{
assert(v->p);
node *p = v->p;
bool s = side(v);
if (p->p)
p->p->c[side(p)] = v;
v->p = p->p;
if (v->c[!s])
v->c[!s]->p = p;
p->c[s] = v->c[!s];
v->c[!s] = p;
p->p = v;
p->cnt -= v->c[s]? 1 + v->c[s]->cnt: 1;
v->cnt += p->c[!s]? 1 + p->c[!s]->cnt: 1;
v->live = p->live;
v->path_par = p->path_par;
}
void splay(node *v)
{
while (v->p && v->p->p) {
side(v) == side(v->p)? rot(v->p): rot(v);
rot(v);
}
if (v->p)
rot(v);
}
void attach_right(node *v, node *r)
{
assert(!v->c[1]);
assert(!r->p);
v->c[1] = r;
r->p = v;
v->cnt += r->cnt;
}
void detach_right(node *v)
{
if (v->c[1]) {
v->c[1]->p = 0;
v->c[1]->path_par = v;
v->cnt -= v->c[1]->cnt;
}
v->c[1] = 0;
}
vector<pii> access(node *v)
{
splay(v);
detach_right(v);
vector<pii> ans = {{v->cnt, v->live}};
while (v->path_par) {
node *u = v->path_par;
splay(u);
detach_right(u);
ans.push_back({u->cnt, u->live});
attach_right(u, v);
splay(v);
}
return ans;
}
void link(node *v, node *u)
{
assert(!v->p && !v->path_par);
assert(!u->p && !u->path_par && !u->c[0]);
u->path_par = v->path_par;
u->cnt += v->cnt;
u->c[0] = v;
v->p = u;
// live will automatically be ok
}
const int N = 100'010;
node nd[N];
int n;
int fen[N];
int fen_get(int r)
{
int ans = 0;
while (r > 0) {
ans += fen[r];
r -= r & -r;
}
return ans;
}
void fen_add(int i, int x)
{
++i;
while (i <= n) {
fen[i] += x;
i += i & -i;
}
}
vector<int *> cmper;
void compress()
{
sort(cmper.begin(),cmper.end(), [](int *x, int *y){return *x<*y;});
int cnt = 0;
Loop (i,0,cmper.size()) {
if (i && *cmper[i-1] != *cmper[i])
++cnt;
*cmper[i] = cnt;
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
vector<int *> cmper;
Loop (i,0,n) {
cin >> nd[i].live;
nd[i].cnt = 1;
cmper.push_back(&nd[i].live);
}
compress();
Loop (i,1,n) {
int v, u;
cin >> v >> u;
--v; --u;
auto tmp = access(&nd[v]);
link(&nd[v], &nd[u]);
ll ans = 0;
for (auto [cnt, x] : tmp) {
ans += (ll)fen_get(x) * cnt;
fen_add(x, cnt);
}
for (auto [cnt, x] : tmp)
fen_add(x, -cnt);
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
