#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
struct STG{
vector<vector<int>> g;
vector<int> t;
int n, k;
STG(int& ns, int& ks, vector<int>& ts){
n = ns;
k = ks;
t = ts;
g.resize(4 * n + k);
build(1, 1, n);
}
void build(int v, int tl, int tr){
if (tl == tr){
g[v + k].pb(t[tl]);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
build(vv, tl, tm);
build(vv + 1, tm + 1, tr);
v += k; vv += k;
g[v].pb(vv); g[v].pb(vv + 1);
}
void add(int v, int tl, int tr, int& l, int& r, int& u){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
g[u].pb(v + k);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
add(vv, tl, tm, l, r, u);
add(vv + 1, tm + 1, tr, l, r, u);
}
void add(int l, int r, int u){
add(1, 1, n, l, r, u);
}
vector<vector<int>> gt;
vector<int> order;
vector<bool> used;
void dfs1(int v){
used[v] = 1;
for (int i: g[v]){
if (!used[i]){
dfs1(i);
}
}
order.pb(v);
}
vector<int> cp, cc;
int cur;
void dfs2(int v){
cp[v] = cur;
cc[cur] += (v <= k);
for (int i: gt[v]){
if (!cp[i]){
dfs2(i);
}
}
}
vector<vector<int>> gg;
vector<int> sz;
void fill(int v){
sz[v] = cc[v];
used[v] = 1;
for (int i: gg[v]){
if (!used[i]){
fill(i);
}
sz[v] += sz[i];
}
}
void scc(){
used.resize(g.size());
for (int i = 1; i <= k + 1; i++){
if (!used[i]) dfs1(i);
}
reverse(order.begin(), order.end());
gt.resize(g.size());
for (int i = 1; i < g.size(); i++){
for (int j: g[i]){
gt[j].pb(i);
}
}
cp.resize(g.size());
cc.resize(g.size());
cur = 0;
for (int i: order){
if (!cp[i]){
cur++;
dfs2(i);
}
}
gg.resize(cur + 1);
for (int i = 1; i < g.size(); i++){
for (int j: g[i]){
if (cp[i] != cp[j]){
gg[cp[i]].pb(cp[j]);
}
}
}
used.assign(cur + 1, 0);
sz.resize(cur + 1);
for (int i = 1; i <= cur; i++){
if (!used[i]){
fill(i);
}
}
int out = k;
for (int i = 1; i <= k; i++){
out = min(out, sz[cp[i]]);
}
cout<<--out<<"\n";
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k; cin>>n>>k;
vector<int> g[n + 1];
for (int i = 1; i < n; i++){
int x, y; cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
vector<int> ct[k + 1], c(n + 1);
for (int i = 1; i <= n; i++){
cin>>c[i];
ct[c[i]].pb(i);
}
vector<int> sz(n + 1), p(n + 1), h(n + 1), d(n + 1);
function<void(int, int)> fill = [&](int v, int pr){
sz[v] = 1;
p[v] = pr;
for (int i: g[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
fill(i, v);
sz[v] += sz[i];
if (sz[i] > sz[h[v]]){
h[v] = i;
}
}
};
fill(1, 0);
vector<int> head(n + 1), pos(n + 1);
int timer = 0;
function<void(int, int)> fill_hld = [&](int v, int H){
head[v] = H;
pos[v] = ++timer;
if (!h[v]) return;
fill_hld(h[v], H);
for (int i: g[v]){
if (pos[i]) continue;
fill_hld(i, i);
}
};
fill_hld(1, 1);
vector<int> t(n + 1);
for (int i = 1; i <= n; i++){
t[pos[i]] = c[i];
}
STG T(n, k, t);
auto add = [&](int x, int y, int i){
while (head[x] != head[y]){
if (d[head[x]] > d[head[y]]) swap(x, y);
T.add(pos[head[y]], pos[y], i);
y = p[head[y]];
}
if (d[x] > d[y]) swap(x, y);
T.add(pos[x], pos[y], i);
};
for (int i = 1; i <= k; i++){
for (int j = 0; j + 1 < ct[i].size(); j++){
add(ct[i][j], ct[i][j + 1], i);
}
}
T.scc();
}
Compilation message
capital_city.cpp: In member function 'void STG::scc()':
capital_city.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 1; i < g.size(); i++){
| ~~^~~~~~~~~~
capital_city.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 1; i < g.size(); i++){
| ~~^~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:195:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int j = 0; j + 1 < ct[i].size(); j++){
| ~~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
3 ms |
1628 KB |
Output is correct |
12 |
Correct |
3 ms |
1628 KB |
Output is correct |
13 |
Correct |
3 ms |
1628 KB |
Output is correct |
14 |
Correct |
3 ms |
1640 KB |
Output is correct |
15 |
Incorrect |
2 ms |
1608 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
399 ms |
157912 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
3 ms |
1628 KB |
Output is correct |
12 |
Correct |
3 ms |
1628 KB |
Output is correct |
13 |
Correct |
3 ms |
1628 KB |
Output is correct |
14 |
Correct |
3 ms |
1640 KB |
Output is correct |
15 |
Incorrect |
2 ms |
1608 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |