#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 200005;
int n, k;
vector<int> clr[MXN];
namespace GRAPH {
int nc;
vector<int> edge[MXN * 20];
int dfn[MXN * 20], low[MXN * 20], scc[MXN * 20], ns, C;
vector<int> st;
int out[MXN * 20];
void ADD_EDGE(int x, int y) {
edge[x].push_back(y);
}
void DFS(int id) {
C++;
dfn[id] = C;
low[id] = C;
st.push_back(id);
for (auto &i : edge[id]) {
if (scc[i]) continue;
if (dfn[i]) {
low[id] = min(low[id], dfn[i]);
} else {
DFS(i);
low[id] = min(low[id], low[i]);
}
}
if (dfn[id] == low[id]) {
int x;
ns++;
do {
x = st.back();
st.pop_back();
scc[x] = ns;
} while (x != id);
}
}
void SCC() {
FOR(i, 1, nc + 1) {
if (dfn[i]) continue;
DFS(i);
}
}
int GET_ANS() {
FOR(id, 1, nc + 1) {
for (auto &i : edge[id]) {
if (scc[i] == scc[id]) continue;
out[scc[id]]++;
}
}
map<int, int> M;
FOR(i, n + 1, n + k + 1) if (out[scc[i]] == 0) M[scc[i]]++;
int ans = INT_MAX;
for (auto i : M) ans = min(ans, i.sc);
return ans;
}
}
namespace TREE {
vector<int> edge[MXN], lf[MXN];
vector<int> p[MXN];
int d[MXN];
void ADD_EDGE(int x, int y) {
edge[x].push_back(y);
edge[y].push_back(x);
}
void DFS(int id, int par, int dep) {
p[id].push_back(par);
d[id] = dep;
for (auto &i : edge[id]) {
if (i == par) continue;
DFS(i, id, dep + 1);
}
}
void LIFT() {
DFS(1, 1, 0);
FOR(i, 1, n + 1) lf[i].push_back(i);
for(int w = 1; (1 << w) <= n; w++) {
debug(w);
FOR(i, 1, n + 1) {
int now = ++GRAPH::nc;
GRAPH::ADD_EDGE(now, lf[i][w - 1]);
GRAPH::ADD_EDGE(now, lf[p[i].back()][w - 1]);
lf[i].push_back(now);
}
FOR(i, 1, n + 1) {
debug(i, p[p[i][w - 1]][w - 1]);
p[i].push_back(p[p[i][w - 1]][w - 1]);
}
}
}
int leap_bin(int x, int w, int c) {
GRAPH::ADD_EDGE(c, lf[x][w]);
return p[x][w];
}
int leap(int x, int k, int c) {
for (int w = __lg(n); w >= 0; w--) {
if (k & w) x = leap_bin(x, w, c);
}
return x;
}
int lca(int x, int y, int c) {
if (d[x] < d[y]) swap(x, y);
x = leap(x, d[x] - d[y], c);
if (x == y) return x;
for (int w = __lg(n); w >= 0; w--) {
if (p[x][w] == p[y][w]) continue;
x = leap_bin(x, w, c);
y = leap_bin(y, w, c);
}
leap_bin(x, 0, c);
leap_bin(y, 0, c);
return p[x][0];
}
void BUILD(vector<int> v, int c) {
debug(c);
// for (auto &i : v) cout << i << ' ';
// cout << endl;
if (v.size() == 1) {
GRAPH::ADD_EDGE(c, lf[v[0]][0]);
return;
}
int lca_now = v.back();
GRAPH::ADD_EDGE(c, lf[lca_now][0]);
v.pop_back();
for (auto &i : v) {
lca_now = lca(lca_now, i, c);
GRAPH::ADD_EDGE(c, lf[lca_now][0]);
}
}
}
void miku() {
int a, b;
cin >> n >> k;
GRAPH::nc = n + k;
FOR(i, 1, n) {
cin >> a >> b;
TREE::ADD_EDGE(a, b);
}
FOR(i, 1, n + 1) {
cin >> a;
clr[a].push_back(i);
GRAPH::ADD_EDGE(i, a + n);
}
TREE::LIFT();
FOR(i, 1, k + 1) {
TREE::BUILD(clr[i], i + n);
}
GRAPH::SCC();
cout << GRAPH::GET_ANS() - 1 << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(iostream::failbit);
miku();
return 0;
}
Compilation message
capital_city.cpp: In function 'void TREE::LIFT()':
capital_city.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
capital_city.cpp:105:13: note: in expansion of macro 'debug'
105 | debug(w);
| ^~~~~
capital_city.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
capital_city.cpp:113:17: note: in expansion of macro 'debug'
113 | debug(i, p[p[i][w - 1]][w - 1]);
| ^~~~~
capital_city.cpp: In function 'void TREE::BUILD(std::vector<int>, int)':
capital_city.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
capital_city.cpp:146:9: note: in expansion of macro 'debug'
146 | debug(c);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
120924 KB |
Output is correct |
| 2 |
Correct |
26 ms |
120924 KB |
Output is correct |
| 3 |
Correct |
26 ms |
120920 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
120924 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
120924 KB |
Output is correct |
| 2 |
Correct |
26 ms |
120924 KB |
Output is correct |
| 3 |
Correct |
26 ms |
120920 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
120924 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2810 ms |
494332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
120924 KB |
Output is correct |
| 2 |
Correct |
26 ms |
120924 KB |
Output is correct |
| 3 |
Correct |
26 ms |
120920 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
120924 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
