#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 5e5 + 5;
int sz[N];
int od, id;
int leaves;
int col[N];
bool bad[N];
int in[N], out[N];
vector<int> vec[N];
vector<int> g[N];
int pre(int v, int p) {
sz[v] = 1;
for (int u : g[v]) {
if (u != p) {
pre(u, v);
sz[v] += sz[u];
}
}
return sz[v];
}
void dfs(int v, int p, bool keep) {
int big = 0;
for (int u : g[v]) {
if (u != p && sz[u] > sz[big]) {
big = u;
}
}
for (int u : g[v]) {
if (u != p && u != big) {
dfs(u, v, false);
}
}
if (big) {
dfs(big, v, true);
swap(vec[v], vec[big]);
}
if (--out[col[v]] == 0) {
od++;
}
if (in[col[v]]++ == 0) {
id++;
}
vec[v].push_back(v);
for (int u : g[v]) {
if (u == p || u == big) {
continue;
}
for (int x : vec[u]) {
if (--out[col[x]] == 0) {
od++;
}
if (in[col[x]]++ == 0) {
id++;
}
vec[v].push_back(u);
}
}
if (od == id) {
bad[v] = true;
}
if (!keep) {
for (int u : vec[v]) {
if (out[col[u]]++ == 0) {
od--;
}
if (--in[col[u]] == 0) {
id--;
}
}
}
}
bool dfs2(int v, int p) {
bool ret = false;
for (int u : g[v]) {
if (u != p) {
ret |= dfs2(u, v);
}
}
if (!ret && bad[v]) {
ret = true;
leaves++;
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
for(int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
cin >> col[i];
out[col[i]]++;
}
pre(1, 1);
dfs(1, 1, 1);
bad[1] = false;
dfs2(1, 1);
cout << (leaves + 1) / 2 << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
29276 KB |
Output is correct |
2 |
Incorrect |
7 ms |
29368 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
29276 KB |
Output is correct |
2 |
Incorrect |
7 ms |
29368 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
29276 KB |
Output is correct |
2 |
Incorrect |
7 ms |
29368 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
38092 KB |
Output is correct |
2 |
Incorrect |
45 ms |
39048 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
29276 KB |
Output is correct |
2 |
Incorrect |
7 ms |
29368 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |