#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Data {
int l, r, c;
};
int n, c[N];
int a[N], b[N];
int par[N], nchild[N];
int T, head[N], pos[N];
int bit[N];
vector<int> G[N];
deque<Data> dq[N];
void dfs(int u) {
nchild[u] = 1;
for (auto v : G[u]) {
dfs(v), nchild[u] += nchild[v];
}
}
void dfsHld(int u) {
if (!head[u]) head[u] = u;
pos[u] = ++T;
int cur = 0;
for (auto v : G[u]) {
nchild[u] += nchild[v];
if (cur == 0 || nchild[cur] < nchild[v]) cur = v;
}
if (cur) head[cur] = head[u];
for (auto v : G[u]) {
dfsHld(v);
}
}
void upd(int x, int y) {
for (; x <= n; x += x & -x) bit[x] += y;
}
int get(int x) {
int ret = 0; for (; x > 0; x -= x & -x) ret += bit[x]; return ret;
}
void updHld(int u, int c) {
while (u) {
int pu = pos[u];
u = head[u];
while (dq[u].size()) {
Data tmp = dq[u].front();
if (tmp.r <= pu) dq[u].pop_front();
else {
dq[u][0].l = pu + 1; break;
}
}
dq[u].push_front({pos[u], pu, c});
u = par[u];
}
}
void getHld(int u) {
long long res = 0;
vector< pair<int, int> > buffer;
while (u) {
int pu = pos[u];
u = head[u];
if (dq[u].size()) {
int ptr = 0;
for (ptr; ptr < dq[u].size(); ++ptr) {
if (pu <= dq[u][ptr].r) break;
}
if (ptr == dq[u].size()) ptr--;
for (ptr; ptr >= 0; --ptr) {
int cnt = min(dq[u][ptr].r, pu) - dq[u][ptr].l + 1;
res += 1LL * get(dq[u][ptr].c - 1) * cnt;
upd(dq[u][ptr].c, cnt);
buffer.push_back({dq[u][ptr].c, -cnt});
}
}
u = par[u];
}
for (auto i : buffer) upd(i.first, i.second);
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
vector<int> vec;
for (int i = 1; i <= n; ++i) cin >> c[i], vec.push_back(c[i]);
sort(vec.begin(), vec.end());
for (int i = 1; i <= n; ++i) c[i] = lower_bound(vec.begin(), vec.end(), c[i]) - vec.begin() + 1;
for (int i = 1; i < n; ++i) {
cin >> a[i] >> b[i], G[a[i]].push_back(b[i]), par[b[i]] = a[i];
}
dfs(1), dfsHld(1);
dq[head[1]].push_back({pos[1], pos[1], c[1]});
for (int i = 1; i < n; ++i) {
getHld(b[i]);
updHld(b[i], c[b[i]]);
// for (int j = 1; j <= n; ++j) {
// if (j == head[j]) {
// cout << "#check dq " << j << '\n';
// for (auto k : dq[j]) {
// cout << k.l << ' ' << k.r << ' ' << k.c << '\n';
// }
// }
// }
}
}
Compilation message
construction.cpp: In function 'void getHld(int)':
construction.cpp:72:12: warning: statement has no effect [-Wunused-value]
for (ptr; ptr < dq[u].size(); ++ptr) {
^
construction.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ptr; ptr < dq[u].size(); ++ptr) {
~~~~^~~~~~~~~~~~~~
construction.cpp:75:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ptr == dq[u].size()) ptr--;
~~~~^~~~~~~~~~~~~~~
construction.cpp:76:12: warning: statement has no effect [-Wunused-value]
for (ptr; ptr >= 0; --ptr) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
68472 KB |
Output is correct |
| 2 |
Correct |
104 ms |
68584 KB |
Output is correct |
| 3 |
Incorrect |
73 ms |
68684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
68472 KB |
Output is correct |
| 2 |
Correct |
104 ms |
68584 KB |
Output is correct |
| 3 |
Incorrect |
73 ms |
68684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
68472 KB |
Output is correct |
| 2 |
Correct |
104 ms |
68584 KB |
Output is correct |
| 3 |
Incorrect |
73 ms |
68684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
