#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define m_p make_pair
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)x.size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long,long long> pll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <class T> using oset=tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N=1e5+3;
struct segtree{
pii t[4*N];
segtree(){
fill(t,t+4*N,m_p(-2e9,1));
}
void upd(int id,pii x,int v=1,int tl=0,int tr=N-1){
if(tl==tr){
umax(t[v],x);
// debug()<<imie(t[v])imie(x);
return;
}
int tm=(tl+tr)>>1;
if(tm>=id)
upd(id,x,2*v,tl,tm);
else
upd(id,x,2*v+1,tm+1,tr);
t[v]=max(t[2*v],t[2*v+1]);
}
pii get(int l,int r,int v=1,int tl=0,int tr=N-1){
if(tl>=l&&tr<=r) return t[v];
if(tl>r||tr<l) return {-2e9,1};
int tm=(tl+tr)>>1;
return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
}seg;
struct fenwick{
int fnw[N];
fenwick(){
fill(fnw,fnw+N,0);
}
vec<pii>up;
void upd(int i,int x,bool t=1){
if(t) up.pb({i,-x});
while(i<N){
fnw[i]+=x;
i+=i&-i;
}
}
int get(int i){
int ans=0;
while(i>0){
ans+=fnw[i];
i-=i&-i;
}
return ans;
}
int get(int l,int r){
return get(r)-get(l-1);
}
void clr(){
// debug()<<imie(up);
for(auto &z : up)
upd(z.f,z.s,0);
up.clear();
}
}fnw;
vec<int> g[N];
int up[N][20],tin[N],tout[N],tt=1;
void dfs(int v,int p){
up[v][0]=p;
tin[v]=tt++;
// debug()<<imie()
for(int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
for(auto &z : g[v]){
if(z==p) continue;
dfs(z,v);
}
tout[v]=tt-1;
// debug()<<imie(v)imie(tin[v])imie(tout[v]);
}
signed main(){
fast_ioi;
// return 0;
int n;
cin>>n;
vec<int>a(n);
for(auto &z : a) cin>>z;
vec<int> kek=a;
sort(all(kek));kek.erase(unique(all(kek)),kek.end());
for(auto &z : a) z=lower_bound(all(kek),z)-kek.begin()+1;
vec<pii>e;
for(int i=1;i<n;i++){
int v, u;
cin >> v >> u;//--v; --u;
e.pb({v,u});
g[v].pb(u);
}
g[0].pb(1);
dfs(0,0);
seg.upd(tin[1],{-1,a[0]});
// return 0;
int sm=0;
for(int i=0;i<n-1;i++){
ll ans=0;
int v=e[i].f;
vec<pii>arr;
while(v){
/// find max u
int cnt=0;
for(int j=19;j>=0;j--){
if(up[v][j]!=0
&&
seg.get(tin[up[v][j]],tout[up[v][j]])==seg.get(tin[v],tout[v]))
v=up[v][j],cnt+=(1<<j);
}
arr.pb({seg.get(tin[v],tout[v]).s,cnt+1});
v=up[v][0];
}
sm+=sz(arr);
assert(sm<=2*n);
// debug()<<imie(arr);
for(auto &z : arr){
ans+=1ll*z.s*fnw.get(z.f-1);
fnw.upd(z.f,z.s);
}
fnw.clr();
cout<<ans<<'\n';
seg.upd(tin[e[i].s],{i,a[e[i].s-1]});
// if(i==1) return 0;
// for(int i=0;i<=n;i++)
// debug()<<imie(i)imie(seg.get(tin[i],tout[i]));
// debug()<<imie(*max_element(fnw.fnw,fnw.fnw+N));
// debug()<<imie()
}
return 0;
}
/*
5
4
0
0
0
1
2
3
0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6092 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6092 KB |
Output is correct |
| 3 |
Runtime error |
8 ms |
12364 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6092 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6092 KB |
Output is correct |
| 3 |
Runtime error |
8 ms |
12364 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6092 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6092 KB |
Output is correct |
| 3 |
Runtime error |
8 ms |
12364 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
