#include <bits/stdc++.h>
using namespace std;
const int UNDEF = 0;
const int MAX_N = 1e5;
int c[MAX_N], parent[MAX_N], ord[MAX_N];
vector<int> edges[MAX_N];
struct vr {
int val, rep;
};
struct info {
vector<vr> v;
info operator + ( info &a ) {
vector<vr> ans = v;
for ( vr x: a.v ) {
if ( !ans.empty() && ans.back().val == x.val )
ans[ans.size() - 1].rep += x.rep;
else
ans.push_back( x );
}
return { ans };
}
};
struct SegTree {
info segTree[4 * MAX_N];
int lazy[4 * MAX_N];
void init() {
for ( int v = 0; v < 4 * MAX_N; v++ )
lazy[v] = UNDEF;
}
void propag( int v, int l, int r ) {
if ( lazy[v] == UNDEF )
return;
segTree[v].v.clear();
segTree[v].v.push_back( { lazy[v], r - l + 1 } );
if ( l != r )
lazy[v * 2 + 1] = lazy[v * 2 + 2] = lazy[v];
lazy[v] = UNDEF;
}
void update( int v, int l, int r, int lu, int ru, int x ) {
//if ( v == 0 )
//printf( "%d %d %d\n", lu, ru, x );
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
lazy[v] = x;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru, x );
update( v * 2 + 2, mid + 1, r, lu, ru, x );
segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
}
info query( int v, int l, int r, int lq, int rq ) {
propag( v, l, r );
if ( l > rq || r < lq )
return {};
if ( lq <= l && r <= rq )
return segTree[v];
int mid = (l + r) / 2;
info a = query( v * 2 + 1, l, mid, lq, rq );
info b = query( v * 2 + 2, mid + 1, r, lq, rq );
return a + b;
}
};
struct HPD {
int n, curPos;
int sz[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], leftPos[MAX_N], rightPos[MAX_N];
SegTree aint;
void dfs( int u, int p ) {
int maxSz = -1;
parent[u] = p;
depth[u] = depth[p] + 1;
sz[u] = 1;
heavy[u] = UNDEF;
for ( int v: edges[u] ) {
if ( v == p )
continue;
dfs( v, u );
sz[u] += sz[v];
if ( sz[v] > maxSz ) {
maxSz = sz[v];
heavy[u] = v;
}
}
}
void decomp( int u, int p, int h ) {
head[u] = h;
leftPos[u] = ++curPos;
if ( heavy[u] != UNDEF )
decomp( heavy[u], u, h );
for ( int v: edges[u] ) {
if ( v == p || v == heavy[u] )
continue;
decomp( v, u, v );
}
rightPos[u] = curPos;
}
void init( int _n ) {
n = _n;
aint.init();
dfs( 1, 0 );
decomp( 1, 0, 1 );
}
void updatePath( int u, int v, int x ) {
while ( head[u] != head[v] ) {
if ( depth[head[u]] < depth[head[v]] )
swap( u, v );
aint.update( 0, 1, n, leftPos[head[u]], leftPos[u], x );
u = parent[head[u]];
}
if ( depth[u] > depth[v] )
swap( u, v );
aint.update( 0, 1, n, leftPos[u], leftPos[v], x );
}
info queryPath( int u, int v ) {
info ans;
while ( head[u] != head[v] ) {
if ( depth[head[u]] < depth[head[v]] )
swap( u, v );
info a = aint.query( 0, 1, n, leftPos[head[u]], leftPos[u] );
ans = a + ans;
u = parent[head[u]];
}
if ( depth[u] > depth[v] )
swap( u, v );
info a = aint.query( 0, 1, n, leftPos[u], leftPos[v] );
ans = a + ans;
return ans;
}
};
struct AIB {
int aib[MAX_N + 1];
void update( int i, int x ) {
while ( i <= MAX_N ) {
aib[i] += x;
i += (i & -i);
}
}
int query( int i ) {
int sum = 0;
while ( i > 0 ) {
sum += aib[i];
i -= (i & -i);
}
return sum;
}
};
AIB aib;
HPD arb;
map<int, int> normal;
int main() {
int n;
cin >> n;
for ( int u = 1; u <= n; u++ )
cin >> c[u], normal[c[u]] = 1;
int val = 0;
for ( auto x: normal )
normal[x.first] = ++val;
for ( int u = 1; u <= n; u++ )
c[u] = normal[c[u]];
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
parent[v] = u;
edges[u].push_back( v );
ord[i] = v;
}
arb.init( n );
arb.updatePath( 1, 1, c[1] );
for ( int i = 0; i < n - 1; i++ ) {
int u = ord[i];
vector<vr> v = arb.queryPath( 1, parent[u] ).v;
int sum = 0;
long long ans = 0;
for ( vr x: v ) {
ans += sum - aib.query( x.val - 1 );
aib.update( x.val, x.rep );
sum += x.rep;
}
for ( vr x: v )
aib.update( x.val, -x.rep );
cout << ans << "\n";
arb.updatePath( 1, u, c[u] );
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
13684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
13652 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
13652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
13684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
13652 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
13652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
13684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
13652 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
13652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
