#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n-1); i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;
void GG(){cout<<"-1\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b) % mo;
}
const int maxn = 1e5+5;
struct BIT{
vector<ll> s;
int MX=0;
ll QU(int e){
ll re = 0; e ++;
while (e>0) {
re+=s[e]; e-=e&(-e);
}return re;
}
void MO(int e, ll v){
e++; while (e<MX){
s[e]+=v; e+=e&(-e);
}
}
BIT(int _mx){
MX = _mx; s.resize(MX+1);
}
};
int top[maxn]; // Lowest depth for this color
int rt[maxn]; // Rightmost child in its sub tree
int at1[maxn], at2[maxn]; // Position for each node in euler tour 1, euler tour 2
int fa[21][maxn], dep[maxn];
int it1 = 0, it2 = 0;
vector<int> g[maxn];
void dfs(int v, int p) {
at1[v] = it1++;
rt[v] = v;
for (int u : g[v]) {
if (u != p) {
dep[u] = dep[v]+1; fa[0][u]= v;
dfs(u,v);
rt[v] = rt[u];
}
}
at2[v] = it2++;
}
int C[maxn];
BIT b1 (maxn), b2(maxn);
vector<int> order;
int kth(int a, int k) {
for (int j = 0; k!=0; j++,k/=2) {
if (k&1) a = fa[j][a];
}
return a;
}
inline void upd(int a, int v) { // Change all ancestors of a (including a) by v
b1.MO(0,v); b2.MO(0,v);
b1.MO(at1[rt[a]]+1,-v);
b2.MO(at2[a],-v);
}
inline int val(int a){
return b1.QU(at1[a])-b2.QU(at2[a]);
}
BIT invbit(maxn+100);
ll inversions(vector<pii> &a){
ll re = 0;
for (pii ele : a) {
re += invbit.QU(ele.f-1) * ele.s;
invbit.MO(ele.f,ele.s);
}
for (pii ele : a) {
invbit.MO(ele.f,-ele.s);
}
return re;
}
signed main(){
IOS();
#ifdef BALBIT
freopen("input.in","r",stdin);
#endif // BALBIT
int n; cin>>n;
vector<int> tmpc(n);
REP(i,n) cin>>tmpc[i];
vector<int> tmpc2 = tmpc;
sort(ALL(tmpc));
REP(i,n) C[i] = lower_bound(ALL(tmpc), tmpc2[i]) - tmpc.begin();
REP(i,n-1) {
int a, b; cin>>a>>b; a--; b--; g[a].pb(b); order.pb(b);
}
dfs(0,-1);
FOR(j,1,21) REP(i,n) {
fa[j][i] = fa[j-1][fa[j-1][i]];
}
fill(top, top+n, 10000000); top[0] = 0; // 1 is already in place
upd(0,C[0]);
for (int B : order){
bug(B);
vector<pii> met; // C-values
upd(B,B);
int chg = B;
int tocol = B;
while (B != 0){
int p = fa[0][B];
int pval = val(p) - chg;
bug(pval);
int odep = dep[B];
int to = top[pval];
int addto = tocol-pval-chg;
chg += addto;
upd(p, addto);
int totop = top[pval];
top[pval] = dep[B];
B = kth(B, totop-dep[B]);
met.pb({C[pval],odep-dep[B]});
bug(B);
}
top[B] = 0;
REP(i,n) {
bug(i+1, val(i));
}
#ifdef BALBIT
for (pii item : met) {
cout<<item.f<<' '<<item.s<<endl;
}
cout<<"====="<<endl;
#endif
cout<<inversions(met)<<"\n";
}
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:159:17: warning: unused variable 'to' [-Wunused-variable]
int to = top[pval];
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Execution timed out |
2029 ms |
71252 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Execution timed out |
2029 ms |
71252 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5368 KB |
Output is correct |
| 2 |
Execution timed out |
2029 ms |
71252 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
