#include<stdio.h>
#include<vector>
using namespace std;
int par[121212][20];
int num[121212], S[121212], E[121212], cnt, tn, depth[121212];;
vector<int>edge[121212];
struct xy { int x, y; }tree[313131];
xy max(xy a, xy b) { if (a.x > b.x)return a; return b; }
void insert_g(int w, xy g) {for (int i = w + tn; i > 0; i /= 2)tree[i] = max(tree[i], g);}
int search_g(int s, int e) {
s += tn; e += tn; xy res;
while (s <= e) {
if (s % 2 == 1)res = max(res, tree[s++]);
if (e % 2 == 0)res = max(res, tree[e--]);
s /= 2; e /= 2;
}
return res.y;
}
void dfs(int w,int bef,int dep) {
par[w][0] = bef; depth[w] = dep;
for (int i = 0; par[w][i] != -1; i++)par[w][i + 1] = par[par[w][i]][i];
num[w] = S[w] = ++cnt;
for (int i = 0; i < edge[w].size(); i++)if (edge[w][i] != bef) {
dfs(edge[w][i], w, dep+1);
}
E[w] = cnt;
}
int get_C(int x) { return search_g(S[x], E[x]); }
int A[121212],B[121212];
int C[121212], CSD[121212];
int go(int a, int b) { for (int i = 0; i < 20; i++)if ((1 << i)&b)a = par[a][i]; return a; }
vector<xy>L;
xy temp[121212];
long long f(int s, int e) {
if (s == e)return 0;
int m = (s + e) / 2, i;
long long res = f(s, m) + f(m + 1, e);
int p1 = s, p2 = m + 1;
int jw = m, S = 0;
for (i = s; i <= m; i++) {
while (jw + 1 <= e&&L[i].x < L[jw + 1].x)S += (long long)L[i].y * L[++jw].y;
res += S;
}
for (i = s; i <= e; i++) {
if (p1 == m + 1 || (p2 != e + 1 && L[p1].x < L[p2].x)) temp[i] = L[p2++];
else temp[i] = L[p1++];
}
for (i = s; i <= e; i++) L[i] = temp[i];
return res;
}
int main() {
int n; scanf("%d", &n);
int i, j;
for (tn = 1; tn < n + 1; tn *= 2);
for (i = 0; i < tn * 2; i++)tree[i].x = -1;
for (i = 1; i <= n; i++)scanf("%d", &C[i]);
for (i = 1; i <= n; i++)for (j = 0; j < 20; j++)par[i][j] = -1;
for (i = 1; i <= n - 1; i++) {
int s, e; scanf("%d%d", &s, &e);
A[i] = s; B[i] = e;
edge[s].push_back(e); edge[e].push_back(s);
}
dfs(1, -1, 0);
CSD[1] = 0; insert_g(1, { 0,1 });
for (i = 1; i <= n - 1; i++) {
L.clear();
int e = B[i], now = par[e][0];
while (now != -1) {
int nowC = get_C(now);
int cs = go(now, depth[now] - CSD[nowC]);
L.push_back({ C[nowC],depth[now] - CSD[nowC] + 1 });
CSD[nowC] = depth[now] + 1;
now = par[cs][0];
}
insert_g(num[e], { i, e });
printf("%lld\n", f(0, L.size() - 1));
}
return 0;
}
Compilation message
construction.cpp: In function 'void dfs(int, int, int)':
construction.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edge[w].size(); i++)if (edge[w][i] != bef) {
~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:52: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:56:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 1; i <= n; i++)scanf("%d", &C[i]);
~~~~~^~~~~~~~~~~~~
construction.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int s, e; scanf("%d%d", &s, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3304 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
3352 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3304 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
3352 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3304 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
3352 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
