// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 1e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 19;
int fen[N];
void Add(int idx, int x){
for(; idx < N; idx += idx & (-idx))
fen[idx] += x;
}
int Get(int idx){
int res = 0;
for(; idx; idx -= idx & (-idx))
res += fen[idx];
return res;
}
int par[N][Log], dep[N];
int val[N], ep[N];
int C[N];
int Blift(int u, int h){
for(int i = 0; i < Log; i++)
if(h >> i & 1)
u = par[u][i];
return u;
}
typedef pair<int, int> pii;
vector<pii> A;
void Solve(int rt, int u, int v){
// cerr << "! " << rt << ' ' << u << ' ' << v << '\n';
if(rt == v) return ;
if(ep[rt] == u){
A.pb({val[rt], dep[v] - dep[rt]});
return ;
}
int v1 = v;
int v2 = ep[rt];
if(dep[v1] > dep[v2])
v1 = Blift(v1, dep[v1] - dep[v2]);
else
v2 = Blift(v2, dep[v2] - dep[v1]);
//assert(v1 != v2);
for(int l = Log - 1; l >= 0; l--){
if(par[v1][l] != par[v2][l])
v1 = par[v1][l], v2 = par[v2][l];
}
A.pb({val[rt], dep[v2] - dep[rt]});
ep[v2] = ep[rt];
val[v2] = val[rt];
Solve(v1, u, v);
return ;
}
ll Calc(){
reverse(all(A));
ll res = 0;
for(auto X : A){
res += 1ll * X.S * Get(X.F - 1);
Add(X.F, X.S);
}
for(auto X : A)
Add(X.F, -X.S);
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> V;
for(int i = 1; i <= n; i++){
cin >> C[i];
V.pb(C[i]);
}
sort(all(V));
for(int i = 1; i <= n; i++){
V[i] = lower_bound(all(V), C[i]) - V.begin();
C[i] += 2;
}
dep[1] = 0;
val[1] = C[1];
ep[1] = 1;
int u, v;
for(int i = 1; i < n; i++){
cin >> u >> v;
par[v][0] = u;
dep[v] = dep[u] + 1;
for(int i = 1; i < Log; i++)
par[v][i] = par[par[v][i - 1]][i - 1];
A.clear();
Solve(1, u, v);
val[1] = C[v];
ep[1] = v;
cout << Calc() << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
