#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
int par[N], rot[N], sz[N], hv[N], c[N], pos[N], n;
long long t[N];
deque<pii> col[N];
vector<pii> qq;
vector<int> g[N];
int dfs( int u, int p ) {
sz[u] = 1, hv[u] = -1, par[u] = p;
for( int v : g[u] ) if( v != p ) {
int mx = -1;
int now = dfs( v, u );
sz[u] += now;
if( now > mx ) mx = now, hv[u] = v;
}
return sz[u];
}
void hld() {
for( int i = 1, idx = 0; i <= n ; i++ ) if( hv[par[i]] != i )
for( int j = i ; j != -1 ; j = hv[j] )
rot[j] = i, pos[j] = ++idx;
}
void up( int idx, long long val ) { for( int i = idx ; i < N ; i += ( i & -i ) ) t[i] += val; }
long long que( int idx, long long ret = 0 ) {
for( int i = idx ; i > 0 ; i -= i & -i ) ret += t[i];
return ret;
}
long long query( int u ) {
long long ret = 0;
vector<int> coord;
vector<pii> ar;
//printf("U:%d\n",u);
while( u ) {
//printf("%d\n",u);
vector<pii> all;
int sz = pos[u] - pos[rot[u]] + 1;
for( pii i : col[rot[u]] ) {
if( i.y >= sz ) {
all.emplace_back( i.x, sz );
break;
}
else all.emplace_back( i ), sz -= i.y;
}
reverse( all.begin(), all.end() );
for( pii i : all ) ar.emplace_back( i ), coord.emplace_back( i.x );
u = par[rot[u]];
}
memset( t, 0, sizeof t );
sort( coord.begin(), coord.end() );
coord.resize( unique( coord.begin(), coord.end() ) - coord.begin() );
for( pii i : ar ) {
//printf("%d %d\n",ar[i].x,ar[i].y);
int x = lower_bound( coord.begin(), coord.end(), i.x ) - coord.begin() + 1;
ret += que( x ) * i.y; up( x, i.y );
}
return ret;
}
void update( int u, int c ) {
while( u ) {
int sz = pos[u] - pos[rot[u]] + 1;
while( !col[rot[u]].empty() ) {
if( col[rot[u]].front().y <= sz ) sz -= col[rot[u]].front().y, col[rot[u]].pop_front();
else {
col[rot[u]].front().y -= sz;
break;
}
}
col[rot[u]].emplace_front( c, pos[u] - pos[rot[u]] + 1 );
u = par[rot[u]];
}
}
int main()
{
scanf("%d",&n);
for( int i = 1 ; i <= n ; i++ ) scanf("%d",&c[i]);
for( int i = 1, s, t ; i < n ; i++ ) {
scanf("%d %d",&s,&t);
g[s].emplace_back( t ), g[t].emplace_back( s );
qq.emplace_back( pii( s, t ) );
}
dfs( 1, 0 ), hld();
col[1].emplace_back( pii( c[1], 1 ) );
for( pii i : qq ) {
printf("%lld\n",query( i.x ) );
update( i.y, c[i.y] );
}
return 0;
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
construction.cpp:87:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for( int i = 1 ; i <= n ; i++ ) scanf("%d",&c[i]);
~~~~~^~~~~~~~~~~~
construction.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&s,&t);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
70784 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
70784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
70784 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
70784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
70784 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
70784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
