//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct BIT{
ll bit[maxn];
vector<pii> ch;
void modify(int ind, int val) {
ch.push_back({ind, val});
for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
}
ll query(int ind) {
ll ret = 0;
for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
return ret;
}
void rev() {
for (auto [ind, val]:ch) {
for (;ind < maxn;ind += ind & (-ind)) bit[ind] -= val;
}
ch.clear();
}
} bit;
vector<int> adj[maxn];
int c[maxn], par[maxn], siz[maxn], dep[maxn], ti[maxn], up[maxn], ord[maxn];
int nxt[maxn];
void getsiz(int n, int pa, int d) {
dep[n] = d;
siz[n] = 1;
for (int v:adj[n]) {
getsiz(v, n, d+1);
siz[n] += siz[v];
}
}
void mark(int n, int pa, int vi) {
up[n] = vi;
int best = 0, bind = 0;
for (int v:adj[n]) {
if (siz[v] > best) {
best = siz[v], bind = v;
}
}
nxt[n] = bind;
for (int v:adj[n]) {
if (v == bind) {
mark(v, n, v);
} else {
mark(v, n, vi);
}
}
}
ll ans[maxn];
vector<pii> se[maxn];
int main() {
io
int n;
cin >> n;
vector<int> val;
for (int i = 1;i <= n;i++) cin >> c[i], val.push_back(c[i]);
sort(val.begin(), val.end());
val.resize(int(unique(val.begin(), val.end()) - val.begin()));
for (int i = 1;i <= n;i++) c[i] = (lower_bound(val.begin(), val.end(), c[i]) - val.begin() + 1);
for (int i = 1;i <= n - 1;i++) {
int u, v;
cin >> u >> v;
par[v] = u;
ti[v] = i;
ord[i] = v;
adj[u].push_back(v);
}
getsiz(1, 0, 0);
mark(1, 0, 1);
se[1].push_back({0, 1});
for (int id = 1;id <= n - 1;id++) {
int i = par[ord[id]], nc = c[ord[id]];
vector<pii> col;
col.push_back({dep[ord[id]], maxn - 1});
while (i) {
//get all segments into col and update
int p = up[i], di = dep[i] + 1, last = 0;
vector<pii> &cur = se[p];
vector<pii> tmp;
int siz = cur.size();
while (siz && cur.back().ff < di) {
last = cur.back().ss;
tmp.push_back(cur.back());
cur.pop_back();
siz--;
}
if (nxt[i] && !(siz && cur.back().ff == di)) cur.push_back({di, last});
cur.push_back({dep[p], nc});
reverse(tmp.begin(), tmp.end());
col.insert(col.end(), tmp.begin(), tmp.end());
i = par[p];
}
i = ord[id];
debug(i);
debug(col[0].ff, col[0].ss);
for (int j = 1;j < col.size();j++) {
debug(col[j].ff, col[j].ss);
ans[i] += bit.query(col[j].ss - 1) * (col[j-1].ff - col[j].ff);
bit.modify(col[j].ss, col[j-1].ff - col[j].ff);
}
if (i == up[i]) {
se[i].push_back({dep[i], c[i]});
}
bit.rev();
}
for (int i = 1;i <= n - 1;i++) cout << ans[ord[i]] << "\n";
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
construction.cpp:121:3: note: in expansion of macro 'debug'
121 | debug(i);
| ^~~~~
construction.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
construction.cpp:122:3: note: in expansion of macro 'debug'
122 | debug(col[0].ff, col[0].ss);
| ^~~~~
construction.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for (int j = 1;j < col.size();j++) {
| ~~^~~~~~~~~~~~
construction.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
construction.cpp:124:4: note: in expansion of macro 'debug'
124 | debug(col[j].ff, col[j].ss);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
