//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int bit[200005];
int lowbit(int x){return x&-x;}
int qsum(int pl){
int ret=0;
while(pl){
ret+=bit[pl];
pl-=lowbit(pl);
}
return ret;
}
vector<pair<int,int>>uvc;
void updbit(int pl,int v){
uvc.push_back({pl,v});
while(pl<=200000){
bit[pl]+=v;
pl+=lowbit(pl);
}
}
void undo(){
int pl=uvc.back().first;int v=uvc.back().second;
v*=-1;
while(pl<=200000){
bit[pl]+=v;
pl+=lowbit(pl);
}
uvc.pop_back();
}
int n;
int ar[200005];
vector<int>e[200005];
int dph[200005];
int hd[200005];
int sbsz[200005];
int fa[200005];
set<pair<pair<int,int>,int>>st[200005];
pair<int,int>qar[200005];
void dfssbsz(int nw,int pa){
dph[nw]=dph[pa]+1;
sbsz[nw]=1;
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i];
dfssbsz(v,nw);
sbsz[nw]+=sbsz[v];
}
for(int i=1;i<e[nw].size();i++){
if(sbsz[e[nw][i]]>sbsz[e[nw][0]]){
swap(e[nw][i],e[nw][0]);
}
}
}
void dfshd(int nw,int head){
hd[nw]=head;
if(e[nw].size()){
dfshd(e[nw][0],head);
}
for(int i=1;i<e[nw].size();i++){
dfshd(e[nw][i],e[nw][i]);
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>ar[i];
}
for(int i=1;i<=n-1;i++){
cin>>qar[i].first>>qar[i].second;
fa[qar[i].second]=qar[i].first;
e[qar[i].first].push_back(qar[i].second);
}
dfssbsz(1,0);
dfshd(1,1);
/*for(int i=1;i<=n;i++){
cout<<hd[i]<<" ";
}cout<<endl;*/
st[1].insert({{1,1},ar[1]});
for(int qqq=1;qqq<=n-1;qqq++){
int nw=qar[qqq].first;
vector<pair<pair<int,int>,int>>fvc;
while(nw!=0){
vector<pair<pair<int,int>,int>>vc;
int hdd=hd[nw];
while(st[hdd].size()){
auto it=st[hdd].begin();
pair<pair<int,int>,int>pr=*it;
if(pr.first.second<=dph[nw]){
vc.push_back(pr);
st[hdd].erase(it);
continue;
}
if(pr.first.first<=dph[nw]){
int ogr=pr.first.second;
pr.first.second=dph[nw];
vc.push_back(pr);
st[hdd].erase(it);
pr={ {dph[nw]+1,ogr} ,pr.second };
st[hdd].insert(pr);
break;
}
break;
}
reverse(vc.begin(),vc.end());
for(int i=0;i<vc.size();i++){
fvc.push_back(vc[i]);
}
nw=fa[hd[nw]];
}
int ans=0;
for(int i=0;i<fvc.size();i++){
int len=fvc[i].first.second-fvc[i].first.first+1;
ans+=len*qsum(fvc[i].second-1);
// cout<<fvc[i].first.first<<" "<<fvc[i].first.second<<" "<<fvc[i].second<<"\n";
updbit(fvc[i].second,len);
}
for(int i=0;i<fvc.size();i++){
undo();
}/*
for(int i=0;i<=200000;i++){
bit[i]=0;
}*/
cout<<ans<<"\n";
nw=qar[qqq].second;
int clr=ar[nw];
while(nw!=0){
int r=dph[nw];
int l=dph[hd[nw]];
st[hd[nw]].insert({{l,r},clr});
nw=fa[hd[nw]];
}
}
}
Compilation message
construction.cpp: In function 'void dfssbsz(long long int, long long int)':
construction.cpp:45:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
construction.cpp:50:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=1;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
construction.cpp: In function 'void dfshd(long long int, long long int)':
construction.cpp:61:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=1;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:115:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0;i<vc.size();i++){
| ~^~~~~~~~~~
construction.cpp:121:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=0;i<fvc.size();i++){
| ~^~~~~~~~~~~
construction.cpp:128:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<fvc.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
42064 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
42064 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
42064 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
