#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 10;
int A[N], B[N], C[N];
vector<int> T[N];
int subt[N];
int dep[N];
int link[N];
int par[N];
void dfs(int u){
subt[u]=1;
for(auto x : T[u]){
dep[x]=dep[u]+1;
par[x]=u;
dfs(x);
subt[u]+=subt[x];
}
}
void hld(int u){
for(auto x : T[u]){
if(subt[x] > (subt[u] + 1) / 2){
link[x]=link[u];
}
else{
link[x]=x;
}
hld(x);
}
}
vector<pii> vals[N];
vector<int> ups;
int lim;
int tree[N * 2];
void upd(int id, int v){
id += lim;
while(id > 0){
tree[id] += v;
ups.push_back(id);
id /= 2;
}
}
int get(int l, int r){
int cnt = 0;
l += lim;
r += lim;
while(l <= r){
if(l % 2 == 1) cnt += tree[l ++];
if(r % 2 == 0) cnt += tree[r --];
l /= 2;
r /= 2;
}
return cnt;
}
ll setv(int node, int bb){
ll ret = 0;
int en;
int len;
int cur;
int low;
vector<pii> lines;
vector<pii> curs;
while(1){
en = link[node];
len = dep[node]-dep[en]+1;
cur = len;
curs.clear();
while(cur > 0){
low = min(cur, vals[en].back().fi);
curs.push_back(mp(low, vals[en].back().se));
vals[en].back().fi -= low;
cur -= low;
if(vals[en].back().fi == 0)
vals[en].pop_back();
}
reverse(curs.begin(), curs.end());
for(auto x : curs)
lines.push_back(x);
vals[en].push_back(mp(len, bb));
if(en == 1) break;
node = par[en];
}
reverse(lines.begin(), lines.end());
ups.clear();
for(auto pq : lines){
ret += get(pq.se + 1, lim - 1);
upd(pq.se, pq.fi);
}
for(auto x : ups){
tree[x]=0;
}
return ret;
}
int main(){
fastIO;
int n;
cin >> n;
vector<int> x;
for(int i = 1; i <= n; i ++ ){
cin >> C[i];
x.push_back(C[i]);
}
sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
lim = x.size();
for(int i = 1; i <= n; i ++ ){
C[i] = lower_bound(x.begin(), x.end(), C[i]) - x.begin();
}
int u, v;
for(int i = 1; i < n; i ++ ){
cin >> A[i] >> B[i];
T[A[i]].push_back(B[i]);
}
link[1]=1;
dfs(1);
hld(1);
par[1]=1;
vals[1].push_back(mp(1, C[1]));
for(int i = 1; i < n; i ++ ){
cout << setv(A[i], C[B[i]]) << "\n";
if(vals[link[B[i]]].empty() || vals[link[B[i]]].back().se != C[B[i]]){
vals[link[B[i]]].push_back(mp(1, C[B[i]]));
}
else{
vals[link[B[i]]].back().fi ++ ;
}
}
return 0;
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:128:9: warning: unused variable 'u' [-Wunused-variable]
128 | int u, v;
| ^
construction.cpp:128:12: warning: unused variable 'v' [-Wunused-variable]
128 | int u, v;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
