#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
#define endl '\n'
struct Kopie {
int x;
int ind;
bool friend operator < (Kopie a, Kopie b) {
return a.x<b.x;
}
};
Kopie d[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int ss[MAXN], par[MAXN];
int heavy[MAXN], start[MAXN], op[MAXN], seg_pos[MAXN];
int heavy_cnt, cnt;
int tree[4*MAXN], lazy[4*MAXN];
int fen[MAXN];
vector <int> v[MAXN];
vector <pair <int,int> > arr;
int n;
void dfs(int x, int p) {
ss[x]=0;
for (auto i:v[x]) {
if (i==p) continue;
dfs(i,x);
par[i]=x;
ss[x]=max(ss[x],ss[i]+1);
}
}
void decompose(int x, int curh) {
seg_pos[x]=cnt;
heavy[x]=curh;
op[cnt]=x;
cnt++;
int maxind=-1;
for (auto i:v[x]) {
if (i==par[x]) continue;
if (maxind==-1 || ss[maxind]<ss[i]) maxind=i;
}
if (maxind==-1) return;
decompose(maxind,curh);
for (auto i:v[x]) {
if (i==par[x] || i==maxind) continue;
heavy_cnt++;
start[heavy_cnt]=i;
decompose(i,heavy_cnt);
}
}
int combine(int l, int r) {
if (l==-2) return r;
if (r==-2) return l;
if (l==r) return l;
return -1;
}
void push_lazy(int node, int l, int r) {
if (!lazy[node]) return;
if (l!=r) {
lazy[node*2]=lazy[node*2+1]=lazy[node];
tree[node*2]=tree[node*2+1]=lazy[node];
}
lazy[node]=0;
}
void update(int node, int l, int r, int ql, int qr, int ch) {
if (ql>r || qr<l) return;
push_lazy(node,l,r);
if (l>=ql && r<=qr) {
tree[node]=lazy[node]=ch;
return;
}
int mid=(l+r)/2;
update(node*2,l,mid,ql,qr,ch);
update(node*2+1,mid+1,r,ql,qr,ch);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
int query(int node, int l, int r, int ql, int qr) {
if (ql>r || qr<l) return -2;
push_lazy(node,l,r);
if (l>=ql && r<=qr) return tree[node];
int mid=(l+r)/2;
return combine(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}
void add_edge(int x, int val) {
while (x!=-1) {
int nxt=start[heavy[x]];
update(1,1,n,seg_pos[nxt],seg_pos[x],val);
x=par[nxt];
}
}
void update_fen(int ind, int ch) {
while (ind<=n) {
fen[ind]+=ch;
ind+=(ind & (-ind));
}
}
int query_fen(int ind) {
int res=0;
while (ind>0) {
res+=fen[ind];
ind-=(ind & (-ind));
}
return res;
}
int find_next(int l, int r, int val) {
int cur=r;
int mid;
while (l<=r) {
mid=(l+r)/2;
if (query(1,1,n,mid,cur)==val) r=mid-1;
else l=mid+1;
}
return op[r];
}
long long find_ans(int x) {
if (!arr.empty()) arr.clear();
int sa=-1;
while (x!=-1) {
int curv=query(1,1,n,seg_pos[x],seg_pos[x]);
arr.push_back({curv,0});
sa++;
int nxt;
while (x!=-1) {
nxt=start[heavy[x]];
int s=query(1,1,n,seg_pos[nxt],seg_pos[x]);
if (s!=curv) break;
arr[sa].second+=seg_pos[x]-seg_pos[nxt]+1;
x=par[nxt];
}
if (x!=-1) {
int newx=find_next(seg_pos[nxt],seg_pos[x],curv);
arr[sa].second+=seg_pos[x]-seg_pos[newx];
x=newx;
}
}
long long ans=0;
for (int i=arr.size()-1;i>=0;i--) {
long long curs=query_fen(n)-query_fen(arr[i].first);
ans+=curs;
update_fen(arr[i].first,arr[i].second);
}
for (int i=0;i<arr.size();i++) update_fen(arr[i].first,-arr[i].second);
return ans;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i=1;i<=n;i++) {
cin >> c[i];
d[i].x=c[i];
d[i].ind=i;
}
sort(d+1,d+n+1);
for (int i=1;i<=n;i++) c[d[i].ind]=i;
for (int i=0;i<n-1;i++) {
cin >> a[i] >> b[i];
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}
dfs(1,-1);
start[1]=1;
heavy_cnt=cnt=1;
par[1]=-1;
decompose(1,1);
update(1,1,n,1,1,1);
for (int i=0;i<n-1;i++) {
cout << find_ans(a[i]) << endl;
add_edge(b[i],c[b[i]]);
}
return 0;
}
Compilation message
construction.cpp: In function 'long long int find_ans(int)':
construction.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for (int i=0;i<arr.size();i++) update_fen(arr[i].first,-arr[i].second);
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
