#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
#define all(x) (x).begin(), (x).end()
using namespace std;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t))cerr<<", ";
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1<<17;
vi E[N];
int pre[N], sz[N], par[N], sci[N], dep[N], val[N], co[N];
int wsk;
void dfs_sz(int v){
for(int u:E[v]){
if(u!=par[v]){
par[u]=v;
dep[u]=dep[v]+1;
dfs_sz(u);
sz[v]+=sz[u];
}
}
sz[v]+=1;
for(int &u:E[v])if(u==par[v])swap(u, E[v].back());
if(v!=1)E[v].pp();
for(int &u:E[v])if(sz[u]>sz[E[v][0]])swap(u, E[v][0]);
//deb(v, E[v].size());
}
void dfs(int v){
co[wsk]=v;
pre[v]=wsk++;
for(int u:E[v]){
//deb(v, u);
if(u==E[v][0])sci[wsk]=sci[pre[v]];
else{
sci[wsk]=wsk;
//deb(v, wsk);
}
dfs(u);
}
}
set<int> S[N];
int sum[N+N];
int add(int v, int c){
int ans=0;
for(v+=N; v; v>>=1){
sum[v]+=c;
if(!(v&1)){
ans+=sum[v+1];
}
}
return ans;
}
ll calc(int v){
vector<pair<int, int> > V;
v=pre[v];
int t=val[v];
bool czy=1;
while(true){
int u=sci[v];
//deb(v, u, S[u].size());
if(S[u].size()){
//deb(*S[u].begin());
}
vector<pair<int, int> > V2;
int prv=u-1;
while(prv<v-czy){
//deb("a");
//assert(S[u].size());
int a=*S[u].begin();
if(a>v-czy){
V2.eb(v-czy-prv, val[a]);
}
else{
V2.eb(a-prv, val[a]);
S[u].erase(a);
}
prv=a;
}
reverse(all(V2));
for(pii &i:V2)V.pb(i);
S[u].insert(v);
val[v]=t;
if(u==0)break;
v=pre[par[co[u]]];
czy=0;
}
reverse(all(V));
//deb(V.size());
for(pii i:V){
//deb(i.st, i.nd);
}
ll ans=0;
for(int i=0; i<V.size(); i++){
ans+=add(V[i].nd, V[i].st);
}
for(int i=0; i<V.size(); i++){
add(V[i].nd, -V[i].st);
}
assert(sum[1]==0);
/*for(int i=0; i<V.size(); i++){
for(int j=0; j<i; j++){
if(V[j].nd>V[i].nd)ans-=V[j].st*1ll*V[i].st;
}
}*/
//assert(ans==0);
return ans;
}
int main(){
//ios_base::sync_with_stdio(0);cin.tie(0);
int n;
cin>>n;
map<int, int> M;
vi V(n);
for(int &i:V)cin>>i, M[i]=1;
int wsk2=1;
for(auto &i:M){
i.nd=wsk2++;
}
vector<pii> edg(n-1);
for(pii &i:edg)cin>>i.st>>i.nd, E[i.st].pb(i.nd), E[i.nd].pb(i.st);
dfs_sz(1);
dfs(1);
for(int i=1; i<=n; i++){
//deb(i, pre[i], par[i], val[i], sci[pre[i]], sz[i]);
}
S[0].insert(0);
for(int i=1; i<=n; i++){
val[pre[i]]=M[V[i-1]];
}
for(pii i:edg){
cout<<calc(i.nd)<<"\n";
}
}
Compilation message
construction.cpp: In function 'll calc(int)':
construction.cpp:108:10: warning: variable 'i' set but not used [-Wunused-but-set-variable]
108 | for(pii i:V){
| ^
construction.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
construction.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9556 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9548 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
9544 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9556 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9548 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
9544 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9556 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9548 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
9544 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
