#include <stdio.h>
#define N 200000
#define M (2*N-2)
#define N_ N+1
#define M_ M+1
#define K N
int n, k, color[N], answer;
/* graph */
int head[N], nxt[M_], vv[M_];
int tin[N], tout[N];
int cfreq[K];
/* node with color */
int head_[K], nxt_[N_], vv_[N_];
void link(int*head, int*nxt, int*vv, int*i, int u, int v)
{
nxt[i[0]] = head[u];
vv[i[0]] = v;
head[u] = i[0]++;
}
void dfs1(int u, int p)
{
static int timer = 0;
tin[u] = timer++;
for (int j = head[u]; j; j = nxt[j])
{
if (vv[j] == p)
continue;
dfs1(vv[j], u);
}
tout[u] = timer - 1;
}
int dead[N], sz[N];
void dfs2(int u, int p)
{
sz[u] = 1;
for (int j = head[u]; j; j = nxt[j])
{
if (vv[j] == p || dead[vv[j]])
continue;
dfs2(vv[j], u);
sz[u] += sz[vv[j]];
}
}
int par[N], visit[N], freq[K], dfreq[K];
void dfs3(int u, int p)
{
visit[u] = -1;
++dfreq[color[u]];
par[u] = p;
for (int j = head[u]; j; j = nxt[j])
{
if (vv[j] == p || dead[vv[j]])
continue;
dfs3(vv[j], u);
}
}
void dfs4(int u, int p)
{
visit[u] = -1;
dfreq[color[u]] = 0;
freq[color[u]] = 0;
for (int j = head[u]; j; j = nxt[j])
{
if (vv[j] == p || dead[vv[j]])
continue;
dfs3(vv[j], u);
}
}
int get_centroid(int u, int p, int tsize)
{
for (int j = head[u]; j; j = nxt[j])
if (!dead[vv[j]] && vv[j] != p && sz[vv[j]] * 2 >= tsize)
return get_centroid(vv[j], u, tsize);
return u;
}
void centroid_decomposition(int u)
{
dfs2(u, u);
u = get_centroid(u, u, sz[u]);
dead[u] = 86;
int col = color[u];
if (dfreq[col] == cfreq[u])
{
dfs3(u, u);
int dcolor = 0;
for (int at, jj = head_[col]; jj; jj = nxt_[jj])
{
at = vv_[jj];
for (;; at = par[at])
{
visit[at] = 1;
if (1 == ++freq[color[at]])
++dcolor;
if (at == u || visit[par[at]] == 1)
break;
}
}
if (dcolor < answer)
answer = dcolor;
dfs4(u, u);
}
for (int j = head[u]; j; j = nxt[j])
if (!dead[vv[j]])
centroid_decomposition(vv[j]);
}
int main()
{
scanf("%d%d", &n, &k);
answer = n;
for (int i = 1, u, v, eo = 0; i < n; ++i)
{
scanf("%d%d", &u, &v); --u, --v;
link(head, nxt, vv, &eo, u, v);
link(head, nxt, vv, &eo, v, u);
}
for (int eo, i = 0; i < n; ++i)
{
scanf("%d", color+i);
++cfreq[color[i]];
link(head_, nxt_, vv_, &eo, color[i], i);
}
dfs1(0, 0);
centroid_decomposition(0);
printf("%d", answer);
}
Compilation message
capital_city.c: In function 'main':
capital_city.c:123:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
capital_city.c:127:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | scanf("%d%d", &u, &v); --u, --v;
| ^~~~~~~~~~~~~~~~~~~~~
capital_city.c:133:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d", color+i);
| ^~~~~~~~~~~~~~~~~~~~
capital_city.c:131:14: warning: 'eo' may be used uninitialized in this function [-Wmaybe-uninitialized]
131 | for (int eo, i = 0; i < n; ++i)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
152 ms |
29452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
