#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int l[100010];
int r[100010];
int p[100010];
int sub[100010];
int pri[100010];
int val[100010];
int par[100010];
void pull(int t){
sub[t] = 1;
if(l[t]!=-1){
sub[t] += sub[l[t]];
p[l[t]] = t;
}
if(r[t]!=-1){
sub[t] += sub[r[t]];
p[r[t]] = t;
}
}
void push(int t){
if(l[t]!=-1){
val[l[t]] = val[t];
}
if(r[t]!=-1){
val[r[t]] = val[t];
}
}
int merge(int le, int ri){
if(le==-1 && ri==-1){
return -1;
}
if(le==-1){
return ri;
}
if(ri==-1){
return le;
}
push(le);
push(ri);
if(pri[le]>pri[ri]){
r[le] = merge(r[le],ri);
pull(le);
return le;
}
else{
l[ri] = merge(le,l[ri]);
pull(ri);
return ri;
}
}
pair<int, int> split(int t, int k){
if(t==-1){
return make_pair(-1,-1);
}
push(t);
int lsum = 0;
if(l[t]!=-1){
lsum = sub[l[t]];
}
if(lsum>=k){
pair<int, int> ret = split(l[t],k);
l[t] = ret.second;
ret.second = t;
pull(t);
// pull(l[t]);
// pull(r[t]);
return ret;
}
else{
pair<int, int> ret = split(r[t],k-lsum-1);
r[t] = ret.first;
ret.first = t;
pull(t);
return ret;
}
}
pair<int, int> dfs(int now, int from){
int ret = 0;
if(from==-1 && l[now]!=-1){
ret += sub[l[now]];
}
if(from!=-1 && r[now]==from){
ret ++;
if(l[now]!=-1){
ret += sub[l[now]];
}
}
if(p[now]==-1){
return make_pair(now,ret);
}
pair<int, int> get = dfs(p[now],now);
get.second += ret;
return get;
}
int first(int now){
if(l[now]==-1){
return now;
}
return first(l[now]);
}
void dfs2(int now){
cout << "NOW " << now << endl;
if(l[now]!=-1){
cout << "LEFT " << now << " -> " << l[now] << endl;
dfs2(l[now]);
}
if(r[now]!=-1){
cout << "RIGHT " << now << " -> " << r[now] << endl;
dfs2(r[now]);
}
}
vector<pair<int, int> > compress(vector<pair<int, int> > a){
vector<int> all;
for(int i = 0; i<a.size(); i++){
all.push_back(a[i].first);
}
sort(all.begin(),all.end());
int p =1;
map<int, int> m;
for(int i = 0; i<a.size(); i++){
if(i==0 || all[i]!=all[i-1]){
m[all[i]] = p++;
}
}
for(int i = 0; i<a.size(); i++){
a[i].first = m[a[i].first];
}
return a;
}
class Fenwick{
public:
vector<ll> li;
int n;
Fenwick(int a){
n = a;
li.resize(n+2);
}
void add(int ind, ll val){
for(;ind<n; ind+=(ind&(-ind))){
li[ind] += val;
}
}
ll get(int ind){
ll ret = 0LL;
for(;ind>0; ind-=(ind&(-ind))){
ret += li[ind];
}
return ret;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
srand(11);
int n;
cin >> n;
for(int i = 0; i<n; i++){
l[i] = -1;
r[i] = -1;
p[i] = -1;
sub[i] = 1;
pri[i] = rand();
cin >> val[i];
par[i] = -1;
}
for(int i = 0; i+1<n; i++){
int a, b;
cin >> a >> b;
a--;
b--;
vector<pair<int, int> > li;
//not including now
int now = a;
int set = val[b];
pair<int, int> got = dfs(now,-1);
int ind = got.second;
int root = got.first;
pair<int, int> both = split(root,ind+1);
p[both.first] = -1;
p[both.second] = -1;
got = dfs(now,-1);
ind = got.second;
root = got.first;
li.push_back(make_pair(val[got.first],1));
while(true){
got = dfs(now,-1);
ind = got.second;
root = got.first;
int f = first(root);
int all = val[root];
if(par[f]==-1){
//started from the bottom, now we here
li.push_back(make_pair(all,ind));
val[root] = set;
now = f;
break;
}
else{
li.push_back(make_pair(all,ind));
int nex = par[f];
pair<int, int> got2 = dfs(nex,-1);
int ind2 = got2.second;
int root2 = got2.first;
pair<int, int> both2 = split(root2,ind2+1);
p[both2.first] = -1;
p[both2.second] = -1;
now = f;
int nval = val[both2.first];
val[merge(both2.first,root)] = nval;
}
}
got = dfs(now,-1);
root = got.first;
par[b] = a;
val[merge(root,b)] = set;
li =compress(li);
Fenwick fen = Fenwick(li.size());
ll all = 0LL;
ll ans = 0LL;
for(int i = li.size()-1; i>=0; i--){
ans += (all-fen.get(li[i].first))*(ll)li[i].second;
fen.add(li[i].first,li[i].second);
all += li[i].second;
}
cout << ans << endl;
}
}
Compilation message
tents.cpp: In function 'std::vector<std::pair<int, int> > compress(std::vector<std::pair<int, int> >)':
tents.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<a.size(); i++){
~^~~~~~~~~
tents.cpp:122:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<a.size(); i++){
~^~~~~~~~~
tents.cpp:127:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<a.size(); i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
