#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
struct Fenwick{
vector<int> bit;
int size;
void modify(int j, int v){
j++;
for(; j < size; j += j & -j)bit[j] += v;
}
int query(int j){
j++;
int v = 0;
for(; j > 0; j -= j & -j)v += bit[j];
return v;
}
int rangequery(int a, int b){
return query(b) - query(a - 1);
}
void rangeupdate(int a, int b, int v){
modify(a, v);
modify(b + 1, -v);
}
Fenwick(int s){
s += 3;
size = s;
bit = vector<int>(s, 0);
}
};
const int N = 1e5 + 5;
vector<int> adj[N];
vector<int> sub(N, 1);
vector<ii> Q;
vector<int> val(N);
vector<int> segind(N, 0);
vector<int> segid(N, 0);
vector<ii> seg[N];
vector<int> who[N];
vector<int> anc(N, 0);
vector<int> depth(N, 0);
vector<ii> ptr(N, {N, 0});
vector<int> S(N, 0);
vector<ii> W;
int ind = 0;
void push(vector<ii>& seg, int j){
if(j * 2 < sz(seg) && seg[j].first != N){
seg[j * 2] = seg[j];
seg[j * 2 + 1] = seg[j];
seg[j] = {N, 0};
}
}
void update(int x){
int id = segid[x];
int ind = segind[x];
ii& p = seg[id][sz(seg[id]) - S[id] + ind];
if(p.first != N) ptr[x] = p;
p = {N, 0};
}
void updown(vector<ii>& seg, int j, int a, int x, int y){
if(x == a && y == a) return;
push(seg, j);
int mid = (x + y) / 2;
if(a <= mid) updown(seg, j * 2, a, x, mid);
else updown(seg, j * 2 + 1, a, mid + 1, y);
}
void update(vector<ii>& seg, int j, int a, int b, int x, int y, ii v){
if(y < a || b < x) return;
if(a <= x && y <= b){
seg[j] = v;
}
else{
update(seg, j * 2, a, b, x, (x + y) / 2, v);
update(seg, j * 2 + 1, a, b, (x + y) / 2 + 1, y, v);
}
}
void update(int x, int v){
int id = segid[x];
int ind = segind[x];
update(seg[id], 1, 0, ind, 0, S[id] - 1, {v, ind});
if(id == 0) return;
update(anc[who[id][0]], v);
}
void query(int x){
int id = segid[x];
int ind = segind[x];
if(id != 0) query(anc[who[id][0]]);
int currind = 0, curr = who[id][0];
while(currind <= ind){
updown(seg[id], 1, currind, 0, S[id] - 1);
update(curr);
int nextind = min(ind, ptr[curr].second);
W.pb({ptr[curr].first, nextind - currind + 1});
currind = nextind + 1;
curr = who[id][currind];
}
}
void build(vector<ii>& seg, int id){
seg = vector<ii> (S[id], {N, 0});
S[id] = (1 << (int)ceil(log2(seg.size())));
int l = S[id] - sz(seg);
for(int i = 0; i < l; i++)seg.pb({N, 0});
reverse(all(seg));
for(int i = 1; i < sz(seg); i += 2) seg.pb({N, 0});
seg.pb({'o','O'});
reverse(all(seg));
}
int dfs(int x, int pre){
for(auto y : adj[x]){
if(y == pre) continue;
anc[y] = x;
depth[y] = depth[x] + 1;
dfs(y, x);
sub[x] += sub[y];
}
}
void dfs_hld(int x, int pre){
int sp = -1;
int mx = -1;
for(auto y : adj[x]){
if(y == pre)continue;
if(mx < sub[y]){
mx = sub[y];
sp = y;
}
}
if(sp == -1)return;
segind[sp] = segind[x] + 1;
segid[sp] = ind;
S[ind]++;
who[ind].pb(sp);
dfs_hld(sp, x);
for(auto y : adj[x]){
if(y == pre || y == sp)continue;
segind[y] = 0;
segid[y] = ++ind;
S[ind]++;
who[ind].pb(y);
dfs_hld(y, x);
}
}
void compress(vector<ii>& arr){
map<int,int> data;
for(auto x : arr) data[x.first] = 0;
int ind = sz(arr);
for(auto& x : data)x.second = ind--;
for(auto& x : arr) x.first = data[x.first];
}
int ans(vector<ii>& arr){
compress(arr);
Fenwick bit(sz(arr));
int ret = 0;
for(auto x : arr){
ret += bit.query(x.first - 1);
bit.modify(x.first, x.second);
}
return ret;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> val[i];
for(int i = 0; i < n - 1; i++){
int x, y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
Q.pb({x, y});
}
dfs(1, 0);
who[0].pb(1);
dfs_hld(1, 0);
for(int i = 0; i <= n; i++) build(seg[i], i);
update(1, val[1]);
for(int i = 0; i < n - 1; i++){
query(Q[i].first);
cout << ans(W) << "\n";
W.clear();
update(Q[i].second, val[Q[i].second]);
}
}
Compilation message
construction.cpp: In function 'long long int dfs(long long int, long long int)':
construction.cpp:134:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
14456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
14456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
14456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
