#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int N = 100005;
int sz[N] , in[N] , out[N] , C[N], t = 0 , ch[N] , depth[N] , inv[N] , pai[N] , endch[N];
vector<int> adj[N];
int n;
vector<pii> edge;
void dfs(int x , int y){
sz[x] = 1;
depth[x] = 0;
depth[x] = depth[y] + 1;
pai[x] = -1;
if(x != y) pai[x] = y;
for(auto &p : adj[x]){
if(p == y) continue;
dfs(p,x);
sz[x] += sz[p];
if(adj[x][0] == y || sz[p] >= sz[adj[x][0]]) swap(p, adj[x][0]);
}
}
int dfs_hld(int x, int y){
in[x] = ++t;
inv[in[x]] = x;
endch[ch[x]] = x;
for(auto p : adj[x]){
if(p == y) continue;
if(p == adj[x][0]) ch[p] = ch[x];
else ch[p] = p;
dfs_hld(p , x);
}
out[x] = t;
}
class ST{
public:
void init(int r ){
st.resize(5*100105);
lazy.resize(5*100105);
}
void propaga(int l, int r , int curr){
if(lazy[curr]){
st[curr] = lazy[curr];
if(l!=r) lazy[2*curr] = lazy[curr] , lazy[2*curr + 1] = lazy[curr];
lazy[curr] = 0;
return ;
}
}
void update(int x , int y , int vl , int l = 1 , int r = 100105 , int curr = 1){
int mid = (l+r)/2;
if(x == l && y == r){
lazy[curr] = vl;
return ;
}
if(y <= mid) update(x,y,vl,l,mid,2*curr);
else if(x > mid) update(x,y,vl,mid+1,r,2*curr +1);
else{
update(x,mid,vl,l,mid,2*curr);
update(mid+1,y,vl,mid+1,r,2*curr+1);
}
}
int query(int x , int l = 1 , int r = 100105, int curr = 1){
int mid = (l+r)/2;
propaga(l,r,curr);
if(x == l && l == r){
return st[curr];
}
if(x <= mid) return query(x,l,mid , 2*curr);
return query(x,mid+1,r,2*curr + 1);
}
private :
vector<int> st , lazy ;
};
ST A , B, D;
map<int,int> ordi;
set<int> sorti;
int BIT[N + 100];
void add(int x , int v){
for(int i = x ; i < (N + 100) ; i += (i&-i)) BIT[i] += v;
}
int get(int x){
int s = 0;
for(int i = x ; i > 0 ; i-= (i&-i)){
s += BIT[i];
}
return s;
}
int32_t main(){
scanf("%d" , &n);
for(int i = 1 ; i <= n; i ++) scanf("%d" , &C[i]) , sorti.insert(C[i]);
int CC = 0;
for(auto p : sorti){
ordi[p] = ++CC;
}
for(int i = 1 ; i <= n; i ++){
C[i] = ordi[C[i]];
}
for(int i = 1 ; i < n ;i ++){
int x , y;
scanf("%d%d" , &x , &y);
adj[x].pb(y);
adj[y].pb(x);
edge.push_back(pii(x,y));
}
A.init(n + 10 ) , B.init(n + 10) , D.init(n + 10);
ch[1] = 1;
dfs(1,1);
dfs_hld(1,1);
B.update(in[1] , in[1] , 1);
A.update(in[1] , in[1] , C[1]);
D.update(in[1] , in[1] , 1);
ch[1] = 1 , pai[1] = -1;
int cnt = 0;
for(auto p : edge){
int L = p.F , R = p.F;
vector<pii> q;
while(L != -1 && R != -1){
L = B.query(in[R]);
q.push_back(pii(A.query(in[R]) , depth[R] - depth[L] + 1));
R = pai[L];
}
reverse(q.begin() , q.end());
long long ans = 0;
for(auto w : q){
add(w.F , w.S);
int U = get(CC + 2) - get(w.F);
long long P = U;
P *= w.S;
ans += P;
}
for(auto w : q){
add(w.F , -w.S);
}
printf("%lld\n" , ans);
cnt++;
L = ch[p.S] , R = p.S;
while(L != -1 && R != -1){
if(adj[R][0] != pai[R] && C[p.S] != A.query(in[adj[R][0]]) && R != p.S && D.query(adj[R][0]) > 0){
// olha o end de cada chain
B.update(in[adj[R][0]] , in[D.query(in[adj[R][0]])] , adj[R][0]);
}
B.update(in[L] , in[R] , L);
A.update(in[L], in[R] , C[p.S]);
D.update(in[L] , in[R] , R);
R = pai[L];
L = ch[R];
}
}
}
/*
10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10
*/
Compilation message
construction.cpp: In function 'int dfs_hld(int, int)':
construction.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
construction.cpp: In function 'int32_t main()':
construction.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &n);
~~~~~^~~~~~~~~~~
construction.cpp:105:52: 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]) , sorti.insert(C[i]);
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &x , &y);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14712 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14728 KB |
Output is correct |
| 3 |
Execution timed out |
2048 ms |
14932 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14712 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14728 KB |
Output is correct |
| 3 |
Execution timed out |
2048 ms |
14932 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14712 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14728 KB |
Output is correct |
| 3 |
Execution timed out |
2048 ms |
14932 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
