#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
int l[100010], r[100010];
int c[100010];
int n;
vector <int> g[100010];
int sub[100010];
int big[100010];
int head[100010];
int pos[100010];
void dfs(int x) {
big[x] = -1;
sub[x] = 1;
for(auto i : g[x]) {
dfs(i);
sub[x] += sub[i];
if(big[x] == -1 || sub[big[x]] < sub[i]) {
big[x] = i;
}
}
}
int mx[100010 * 4];
int mn[100010 * 4];
int prop[100010 * 4];
int par[100010];
int dp[20][100010];
const int logn = 19;
void pushdown(int c) {
if(prop[c] == -1) return ;
int l = c << 1;
int r = l + 1;
prop[l] = prop[r] = prop[c];
mx[l] = mx[r] = prop[c];
mn[l] = mn[r] = prop[c];
prop[c] = -1;
}
void update(int x, int y, int val, int c = 1, int b = 1, int e = n) {
if(x <= b && e <= y) {
mn[c] = mx[c] = val;
prop[c] = val;
return ;
}
if(y < b || e < x) return ;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
update(x, y, val, l, b, m);
update(x, y, val, r, m+1, e);
mn[c] = min(mn[l], mn[r]);
mx[c] = max(mx[l], mx[r]);
}
int query(int x, int val, int c = 1, int b = 1, int e = n) {
if(mx[c] == mn[c]) {
return mx[c] == val ? x - b + 1 : 0;
}
if(b == e) return mx[c] == val;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) return query(x, val, l, b, m);
else {
int len = query(x, val, r, m + 1, e);
if(x - m == len) {
return query(m, val, l, b, m) + len;
} else {
return len;
}
}
}
int get(int x, int c = 1, int b = 1, int e = n) {
if(b == e) return mx[c];
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) return get(x, l, b, m);
else return get(x, r, m+1, e);
}
void precalc() {
memset(prop, -1, sizeof prop);
int cur = 0;
for(int i = 1; i <= n; i++) {
if(par[i] == -1 || big[par[i]] != i) {
for(int j = i; j != -1; j = big[j]) {
pos[j] = ++cur;
head[j] = i;
}
}
}
for(int i = 1; i <= n; i++) {
update(pos[i], pos[i], c[i]);
}
dp[0][1] = 0;
for(int i = 2; i <= n; i++) dp[0][i] = par[i];
for(int i = 1; i <= logn; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
}
void change(int x) {
int cur = x;
while(cur != -1) {
update(pos[head[cur]], pos[cur], c[x]);
cur = head[cur];
cur = par[cur];
}
}
int lift(int node, int up) {
for(int i = logn; i >= 0; i--) {
if((1 << i) <= up) {
node = dp[i][node];
up -= 1 << i;
}
}
return node;
}
int bit[100010];
void upd(int x, int val) {
x += 1;
for(int i = x; i <= n; i += i & (-i)) {
bit[i] += val;
}
}
int total(int x) {
x += 1;
int ans = 0;
for(int i = x; i > 0; i -= i & (-i)) {
ans += bit[i];
}
return ans;
}
long long inverse(vector <pii> v) {
long long ans = 0;
vector <int> idx;
for(int i = 0; i < v.size(); i++) {
idx.push_back(i);
}
auto cmp = [&v] (int a, int b) {
if(v[a].first == v[b].first) return a < b;
else return v[a] < v[b];
};
sort(idx.begin(), idx.end(), cmp);
for(int i : idx) {
ans += v[i].second * total(i);
upd(i, v[i].second);
}
for(auto i : idx) {
upd(i, -v[i].second);
}
return ans;
}
long long getCost(int x) {
vector <pii> v;
int cur = par[x];
while(cur > 0) {
int val = get(pos[cur]);
int len = min(query(pos[cur], val), pos[cur] - pos[head[cur]] + 1);
v.push_back(pii(val, len));
cur = lift(cur, len);
}
return inverse(v);
}
int main(int argc, char const *argv[])
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
}
par[1] = -1;
for(int i = 1; i < n; i++) {
scanf("%d %d", &l[i], &r[i]);
g[l[i]].push_back(r[i]);
par[r[i]] = l[i];
}
dfs(1);
precalc();
for(int i = 1; i < n; i++) {
printf("%lld\n", getCost(r[i]));
change(r[i]);
}
return 0;
}
Compilation message
construction.cpp: In function 'long long int inverse(std::vector<std::pair<int, int> >)':
construction.cpp:146:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
construction.cpp: In function 'int main(int, const char**)':
construction.cpp:176:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
construction.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &c[i]);
~~~~~^~~~~~~~~~~~~
construction.cpp:182:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l[i], &r[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4456 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
4456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4456 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
4456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4456 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
4456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
