#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
struct vr {
int val, rep;
};
const int UNDEF = 0;
const int INF = 1e9;
const int MAX_N = 1e5;
const int MAX_LOG_N = 17;
int c[MAX_N], parent[MAX_LOG_N + 1][MAX_N], ord[MAX_N];
vector<int> edges[MAX_N];
vr elem[MAX_N];
struct info {
int minn, maxx;
info operator + ( info &x ) const {
return { min( minn, x.minn ), max( maxx, x.maxx ) };
}
};
struct SegTree {
info segTree[4 * MAX_N];
int lazy[4 * MAX_N];
void init() {
for ( int v = 0; v < 4 * MAX_N; v++ ) {
segTree[v] = { INF, -INF };
lazy[v] = UNDEF;
}
}
void propag( int v, int l, int r ) {
if ( lazy[v] == UNDEF )
return;
segTree[v] = { lazy[v], lazy[v] };
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 ) {
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 { INF, -INF };
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[0][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();
parent[0][1] = UNDEF;
dfs( 1, UNDEF );
decomp( 1, UNDEF, 1 );
}
void updatePath( int u, int x ) {
while ( u != 0 ) {
aint.update( 0, 1, n, leftPos[head[u]], leftPos[u], x );
u = parent[0][head[u]];
}
}
info queryPath( int u, int v ) {
info ans = { INF, -INF };
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 = ans + a;
u = parent[0][head[u]];
}
if ( depth[u] > depth[v] )
swap( u, v );
info a = aint.query( 0, 1, n, leftPos[u], leftPos[v] );
ans = ans + a;
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() {
ios_base::sync_with_stdio( false );
cin.tie( 0 );
cout.tie( 0 );
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[0][v] = u;
edges[u].push_back( v );
ord[i] = v;
}
for ( int pas = 1; pas <= MAX_LOG_N; pas++ ) {
for ( int u = 1; u <= n; u++ )
parent[pas][u] = parent[pas - 1][parent[pas - 1][u]];
}
arb.init( n );
arb.updatePath( 1, c[1] );
for ( int i = 0; i < n - 1; i++ ) {
int u = ord[i];
int elemSize = 0;
int v = parent[0][u];
while( v != UNDEF ) {
int c = arb.queryPath( v, v ).minn;
int nr = 1;
for ( int pas = MAX_LOG_N; pas >= 0; pas-- ) {
if ( parent[pas][v] != UNDEF && arb.queryPath( u, parent[pas][v] ).maxx == c ) {
v = parent[pas][v];
nr += (1 << pas);
}
}
elem[elemSize++] = { c, nr };
v = parent[0][v];
}
long long ans = 0;
for ( int i = 0; i < elemSize; i++ ) {
vr x = elem[i];
ans += (long long)x.rep * aib.query( x.val -1 );
aib.update( x.val, x.rep );
}
for ( int i = 0; i < elemSize; i++ ) {
vr x = elem[i];
aib.update( x.val, -x.rep );
}
cout << ans << "\n";
arb.updatePath( u, c[u] );
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
7508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
7508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
7508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
