#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5 + 5, N = 1e6;
const ll oo = 1e9 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, c[nmax];
pii a[nmax];
int sz[nmax], par[nmax];
vector<int> adj[nmax];
void dfs(int u, int p){
sz[u] = 1;
for(auto v : adj[u]){
if(v == p) continue;
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
int head[nmax], ind[nmax], pos[nmax], Time = 0, nchain = 1;
int rev[nmax];
void dfs_2(int u, int p){
if(!head[nchain]) head[nchain] = u;
pos[++Time] = u;
ind[u] = nchain;
int idx =-1;
for(auto v : adj[u]){
if(v == p) continue;
if(idx == -1 || sz[idx] < sz[v]){
idx = v;
}
}
if(idx != -1) dfs_2(idx, u);
for(auto v : adj[u]){
if(v == p) continue;
if(idx == v) continue;
++nchain;
dfs_2(v, u);
}
}
vector<pii> one;
struct Seg{
int ma[1 << 18], mi[1 << 18], lz[1 << 18];
void combine(int id){
ma[id] = max(ma[id << 1], ma[id << 1 | 1]);
mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
}
void build(int id, int l, int r){
lz[id] = -1;
if(l == r){
ma[id] = mi[id] = c[pos[l]];
return;
}
int mid = r+ l >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
combine(id);
}
void fix(int id, int val){
if(val == -1) return;
ma[id] = val;
mi[id] = val;
lz[id] = val;
}
void down(int id){
fix(id << 1, lz[id]);
fix(id << 1| 1, lz[id]);
lz[id] = -1;
}
void update(int id, int l, int r, int u, int v, int val){
if(l > v || r < u) return;
if(l >= u && r <= v) return fix(id, val);
down(id);
int mid = r + l >> 1;
update(id << 1, l, mid, u, v,val);
update(id << 1 | 1, mid + 1, r, u, v,val);
combine(id);
}
void get(int id, int l, int r, int u, int v){
if(l > v || r < u) return;
if(l >= u && r <= v && ma[id] == mi[id]){
one.push_back({r - l + 1, ma[id]});
return;
}
down(id);
int mid = r + l >> 1;
get(id << 1 | 1, mid + 1, r, u, v);
get(id << 1, l, mid, u, v);
}
}tree;
struct FEN{
ll f[nmax];
vector<int> tmp;
void update(int x, int val){
for(; x <=n; x += x&-x) f[x] += val, tmp.push_back(x);
}
ll get(int x){
ll cur = 0;
for(; x; x -= x&-x) cur += f[x];
return cur;
}
void clear(){
for(auto p : tmp) f[p] = 0;
tmp.clear();
}
}F;
ll calc(int u, int x){
int A = u, B = x;
int uchain = ind[u];
one.clear();
while(1){
if(uchain == 1){
tree.get(1, 1, n, pos[1], pos[u]);
tree.update(1, 1, n, pos[1], pos[u], c[x]);
break;
}
tree.get(1, 1, n, pos[head[uchain]], pos[u]);
tree.update(1, 1, n, pos[head[uchain]], pos[u], c[x]);
u = par[head[uchain]];
uchain = ind[u];
}
ll ans = 0;
// cout << u << ' ' << x << "#"<<endl;
for(auto [x, y] : one){
ans += 1ll * F.get(y - 1) * x;
F.update(y, x);
// cout << x << ' ' << y << endl;
}
F.clear();
return ans;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n;
vector<int> nen;
for(int i = 1; i <= n; ++i) cin >> c[i],nen.push_back(c[i]);
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
for(int i = 1; i <= n; ++i) c[i] = lower_bound(nen.begin(), nen.end(),c[i]) - nen.begin() + 1;
for(int i = 1; i < n; ++i){
int x, y;
cin >> a[i].fi >> a[i].se;
adj[a[i].fi].push_back(a[i].se);
}
dfs(1, -1);
dfs_2(1, -1);
tree.build(1, 1, n);
ll ans = 0;
for(int i = 1; i < n; ++i){
int x = a[i].fi, y = a[i].se;
cout << calc(x, y) << endl;
}
}
/*
*/
Compilation message
construction.cpp: In member function 'void Seg::build(int, int, int)':
construction.cpp:64:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int mid = r+ l >> 1;
| ~^~~
construction.cpp: In member function 'void Seg::update(int, int, int, int, int, int)':
construction.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid = r + l >> 1;
| ~~^~~
construction.cpp: In member function 'void Seg::get(int, int, int, int, int)':
construction.cpp:96:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int mid = r + l >> 1;
| ~~^~~
construction.cpp: In function 'long long int calc(int, int)':
construction.cpp:118:9: warning: unused variable 'A' [-Wunused-variable]
118 | int A = u, B = x;
| ^
construction.cpp:118:16: warning: unused variable 'B' [-Wunused-variable]
118 | int A = u, B = x;
| ^
construction.cpp: At global scope:
construction.cpp:142:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
142 | main(){
| ^~~~
construction.cpp: In function 'int main()':
construction.cpp:154:13: warning: unused variable 'x' [-Wunused-variable]
154 | int x, y;
| ^
construction.cpp:154:16: warning: unused variable 'y' [-Wunused-variable]
154 | int x, y;
| ^
construction.cpp:161:8: warning: unused variable 'ans' [-Wunused-variable]
161 | ll ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
