#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];
int dep[100010];
int order[100010];
void dfs(int x) {
big[x] = -1;
sub[x] = 1;
for(auto i : g[x]) {
dep[i] = 1 + dep[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 queryMin(int x, int y, int c = 1, int b = 1, int e = n) {
if(x <= b && e <= y) return mn[c];
if(y < b || e < x) return INT_MAX;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
return min(queryMin(x, y, l, b, m), queryMin(x, y, r, m+1, e));
}
int queryMax(int x, int y, int c = 1, int b = 1, int e = n) {
if(x <= b && e <= y) return mx[c];
if(y < b || e < x) return INT_MIN;
pushdown(c);
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
return max(queryMax(x, y, l, b, m), queryMax(x, y, r, m+1, e));
}
int search(int b, int e, int idx) {
if(b == e) {
return idx - b + 1;
}
int m = (b + e) >> 1;
if(queryMin(m, idx) == queryMax(m, idx)) return search(b, m, idx);
else return search(m + 1, e, idx);
}
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;
order[pos[j]] = j;
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) {
if(dep[node] < up) return 0;
for(int i = logn; i >= 0; i--) {
if((1 << i) <= up) {
node = dp[i][node];
up -= 1 << i;
}
}
return node;
}
long long inverse(vector <pii> v) {
long long ans = 0;
for(int i = 0; i < v.size(); i++) {
for(int j = i + 1; j < v.size(); j++) {
if(v[i].first < v[j].first) ans += 1LL * v[i].second * v[j].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 = search(1, pos[cur], pos[cur]); // query(pos[cur], val);
v.push_back(pii(val, len));
// cur = lift(cur, len);
while(len--) cur = par[cur];
}
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:164:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
construction.cpp:165:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = i + 1; j < v.size(); j++) {
~~^~~~~~~~~~
construction.cpp: In function 'int main(int, const char**)':
construction.cpp:185:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
construction.cpp:187:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &c[i]);
~~~~~^~~~~~~~~~~~~
construction.cpp:191: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 |
Correct |
5 ms |
4456 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
4524 KB |
Output isn't correct |
| 5 |
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 |
Correct |
5 ms |
4456 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
4524 KB |
Output isn't correct |
| 5 |
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 |
Correct |
5 ms |
4456 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
4524 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
