#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()
typedef tuple<int, int, int> t3;
int N, C[100010];
int In[100010][2];
vector <int> E[100010];
int st[100010], en[100010], ce;
int up[100010][20], dep[100010];
void dfs(int x, int fa) {
st[x] = ++ce;
for(int e : E[x]) if(e != fa) {
dep[e] = dep[x] + 1;
up[e][0] = x;
for(int i=1;i<20;i++) up[e][i] = up[ up[e][i-1] ][i-1];
dfs(e, x);
}
en[x] = ce;
}
const int TADD = 1<<17;
int T[1<<18];
int get_max(int l, int r) {
l += TADD, r += TADD;
int res = 0;
while(l <= r) {
if(l&1) res = max(res, T[l++]);
if(!(r&1)) res = max(res, T[r--]);
l >>= 1, r >>= 1;
}
return res;
}
int get_node(int x) { return get_max(st[x], en[x]); }
void upd(int x, int v) {
x += TADD;
while(x) T[x] = v, x >>= 1;
}
int stamp;
int max_bit[100010];
int bt[100010];
void updb(int x, int v) {
for(int i=x;i<100010;i+=(i&-i)) bt[i] += v;
}
int readb(int x) {
int res = 0;
for(int i=x;i;i-=(i&-i)) res += bt[i];
return res;
}
ll Do(vector <t3> &X) {
sort(all(X), [](t3 a, t3 b) {
if(get<1>(a) != get<1>(b)) return get<1>(a) < get<1>(b);
return get<2>(a) > get<2>(b);
});
ll res = 0;
for(t3 &e : X) {
res += (ll) get<0>(e) * readb(get<2>(e));
updb(get<2>(e), get<0>(e));
}
for(t3 &e : X) {
updb(get<2>(e), -get<0>(e));
}
return res;
}
void solve(){
for(int i=1;i<100010;i++) max_bit[i] = 31 - __builtin_clz(i);
scanf("%d", &N);
vector <int> vc;
for(int i=1;i<=N;i++) scanf("%d", C + i), vc.pb(C[i]);
sort(all(vc)); vc.resize(unique(all(vc)) - vc.begin());
for(int i=1;i<=N;i++) C[i] = (int)(lower_bound(all(vc), C[i]) - vc.begin() + 1);
for(int i=1;i<N;i++) {
int x, y; scanf("%d%d", &x, &y);
In[i][0] = x, In[i][1] = y;
E[x].pb(y);
}
dfs(1, -1);
upd(st[1], ++stamp);
for(int i=1;i<N;i++) {
int b = In[i][1], a = In[i][0];
vector <t3> R;
while(a) {
int val = get_node(a);
int cnt = 1;
for(int j=max_bit[dep[a]];j>=0;j--) {
int val2 = get_node(up[a][j]);
if(val == val2) {
cnt += 1<<j;
a = up[a][j];
}
}
int nr = szz(R);
R.pb(t3(cnt, C[val], 1 + nr));
a = up[a][0];
}
printf("%lld\n", Do(R));
upd(st[b], ++stamp);
}
}
int main(){
int Tc = 1; //scanf("%d", &Tc);
for(int tc=1;tc<=Tc;tc++){
solve();
}
return 0;
}
Compilation message
construction.cpp: In function 'void solve()':
construction.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
construction.cpp:93:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=N;i++) scanf("%d", C + i), vc.pb(C[i]);
^
construction.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3232 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
3268 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3232 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
3268 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3232 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
3268 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
