#include <bits/stdc++.h>
using namespace std;
struct maxseg {
vector<int> T;
void upd(int idx, int s, int e, int p, int v) {
if(p < s || e < p) return;
if(s == e) {
T[idx] = v;
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, p, v);
upd(idx*2+1, m+1, e, p, v);
T[idx] = max(T[idx*2], T[idx*2+1]);
}
int get(int idx, int s, int e, int l, int r) {
if(r < s || e < l) return 0;
if(l <= s && e <= r) return T[idx];
int m = s+e >> 1;
return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
}
maxseg(int N) {
T.resize(4*N);
}
};
const int _N = 100009;
int A[_N], B[_N], C[_N], in[_N], ou[_N], t, p[22][_N], l, F[_N];
vector<int> adj[_N], CS;
void upd(int x, int y) {
for(int i=x; i<=(int)CS.size(); i+=(i&-i)) F[i] += y;
}
int get(int x) {
int ret = 0;
for(int i=x; i>=1; i-=(i&-i)) ret += F[i];
return ret;
}
void dfs(int x, int p) {
::p[0][x] = p; in[x] = ++t;
for(auto& it: adj[x]) dfs(it, x);
ou[x] = t;
}
int main() {
int N; scanf("%d",&N);
for(int i=1; i<=N; i++) {
scanf("%d",&C[i]);
CS.push_back(C[i]);
}
sort(CS.begin(), CS.end());
CS.resize(unique(CS.begin(), CS.end()) - CS.begin());
for(int i=1; i<=N; i++) C[i] = lower_bound(CS.begin(), CS.end(), C[i]) - CS.begin() + 1;
for(int i=1; i<N; i++) {
scanf("%d%d",&A[i],&B[i]);
adj[A[i]].push_back(B[i]);
}
dfs(1, 1);
for(int i=1; (1<<i)<=N; i++) {
for(int j=1; j<=N; j++) p[i][j] = p[i-1][p[i-1][j]];
l = i;
}
maxseg seg(N); B[0] = 1;
for(int i=1; i<N; i++) {
int now = A[i], nc = C[B[seg.get(1, 1, N, in[now], ou[now])]];
vector<int> S = {nc};
while(now != 1) {
for(int i=l; i>=0; i--) if(nc == C[B[seg.get(1, 1, N, in[p[i][now]], ou[p[i][now]])]]) now = p[i][now];
now = p[0][now]; nc = C[B[seg.get(1, 1, N, in[now], ou[now])]];
S.push_back(nc);
}
seg.upd(1, 1, N, in[B[i]], i);
long long ans = 0;
for(auto& it: S) {
ans += get(it - 1);
upd(it, +1);
}
for(auto& it: S) upd(it, -1);
printf("%lld\n", ans);
}
return 0;
}
Compilation message
construction.cpp: In member function 'void maxseg::upd(int, int, int, int, int)':
construction.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
construction.cpp: In member function 'int maxseg::get(int, int, int, int, int)':
construction.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
construction.cpp: In function 'int main()':
construction.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N; scanf("%d",&N);
~~~~~^~~~~~~~~
construction.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&C[i]);
~~~~~^~~~~~~~~~~~
construction.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&A[i],&B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
