#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>edge[212121], L[2][212121]; int color[212121];
int depth[2][212121], D[2][212121], nxtD[2][212121], mx, mxw;
void dfs(int fl, int w, int bef, int dep) {
depth[fl][w] = dep; D[fl][w] = 0;
if (mx < dep)mx = dep, mxw = w;
for (int nxt : edge[w])if (nxt != bef) {
dfs(fl, nxt, w, dep + 1);
if (D[fl][w] < D[fl][nxt] + 1)nxtD[fl][w] = nxt;
D[fl][w] = max(D[fl][w], D[fl][nxt] + 1);
}
}
int P[2][212121], ans[2][212121], cnt;
int colorCnt, cN[212121];
void coloring(int color, int cnt) {
int befC = !!cN[color]; cN[color] += cnt;
if (befC != !!cN[color]) colorCnt += cnt;
}
int eraseC[212121];
void prColor(int fl, int w, int len, int cnt) {
int now = w;
for (int i = 0; i < len; i++) {
if (now < 0)break;
int befC = !!eraseC[now]; eraseC[now] += cnt;
if (befC != !!eraseC[now])coloring(color[now], -cnt);
now = P[fl][now];
}
}
void get_ans(int fl, int w, int bef, int is_mxline) {
for (int g : L[fl][w]) if (g > 0) prColor(fl, g, 1, -1);
P[fl][w] = bef;
if (bef > 0 && edge[w].size() == 1) {
ans[fl][w] = colorCnt;
for (int g : L[fl][w]) if (g > 0) prColor(fl, g, 1, 1);
return;
}
if (!is_mxline) {
prColor(fl, P[fl][w], D[fl][w], 1);
int now = w, len = D[fl][w];
vector<int>x, y;
for (int i = 0; i < len; i++) { if (now > 0)now = P[fl][now]; x.push_back(now); }
x.push_back(w); now = w;
for (int i = 0; i < len; i++) { now = nxtD[fl][now]; x.push_back(now); y.push_back(now); }
for (int i = 0, j = 0; i < len; i++, j += 2) {
int a = y[i], b = x[j], c = x[j + 1];
L[fl][a].push_back(b); L[fl][a].push_back(c);
}
}
ans[fl][w] = colorCnt;
coloring(color[w], 1);
int mx = 0;
for (int nxt : edge[w]) if (nxt != bef && nxt != nxtD[fl][w]) {
get_ans(fl, nxt, w, 0);
if (mx < D[fl][nxt] + 1) mx = D[fl][nxt] + 1;
}
prColor(fl, w, 1, 1);
prColor(fl, P[fl][w], mx, 1);
get_ans(fl, nxtD[fl][w], w, 1);
prColor(fl, P[fl][w], mx, -1);
if (!is_mxline) {
prColor(fl, P[fl][w], D[fl][w], -1);
}
prColor(fl, w, 1, -1); coloring(color[w], -1);
for (int g : L[fl][w]) if (g > 0) prColor(fl, g, 1, 1);
}
int main() {
int n, m, i, j; scanf("%d%d", &n, &m);
if (n == 1) { printf("0"); return 0; }
for (i = 0; i < n - 1; i++) {
int s, e; scanf("%d%d", &s, &e);
edge[s].push_back(e); edge[e].push_back(s);
}
for (i = 1; i <= n; i++)scanf("%d", &color[i]);
int l, r;
mx = mxw = -1; dfs(0, 1, -1, 0); l = mxw;
mx = mxw = -1; dfs(0, l, -1, 0); r = mxw;
dfs(1, r, -1, 0);
get_ans(0, l, -1, 0);
get_ans(1, r, -1, 0);
for (i = 1; i <= n; i++) {
if (depth[0][i] < depth[1][i]) printf("%d\n", ans[1][i]);
else printf("%d\n", ans[0][i]);
}
return 0;
}
Compilation message
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:73:15: warning: unused variable 'j' [-Wunused-variable]
int n, m, i, j; scanf("%d%d", &n, &m);
^
joi2019_ho_t5.cpp:73:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, m, i, j; scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:76: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);
~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:79: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", &color[i]);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
15352 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
15608 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
282 ms |
29664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
409 ms |
34940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
15352 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
15608 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
