| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1315888 | aaaaaaaa | Capital City (JOI20_capital_city) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 2e5 + 100;
vector<int> adj[mxN], col[mxN];
int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
void dfs(int u, int par){
parent[u] = par;
for(auto it : adj[u]){
if(!vis[it] && it ^ par && !vis_col[id[it]]) dfs(it, u);
}
}
void calc_sz(int u, int par){
sz[u] = 1;
for(auto it : adj[u]){
if(!vis[it] && it ^ par && !vis_col[id[it]]){
calc_sz(it, u);
sz[u] += sz[it];
}
}
}
int find_cent(int u, int par, int nby2){
for(auto it : adj[u]){
if(!vis[it] && it ^ par && !vis_col[id[it]] && sz[it] >= nby2){
return find_cent(it, u, nby2);
}
}
return u;
}
void decompose(int u = 1, int par = -1){
calc_sz(u, -1);
int cent = find_cent(u, -1, sz[u] / 2);
dfs(cent, -1);
queue<int> q;
q.push(id[cent]);
vector<int> cvis(k + 1, 0);
int cans = 0;
while(q.size()){
auto tp = q.front();
q.pop();
if(vis_col[tp]){
cans = mxN;
}
if(cvis[tp]) continue;
cvis[tp] = 1;
cans += 1;
for(auto it : col[tp]){
if(parent[it] != -1){
if(vis_col[id[parent[it]]]){
cans = mxN;
break;
}
if(!cvis[id[parent[it]]]){
q.push(id[parent[it]]);
//cvis[id[parent[it]]] = 1;
}
}
}
}
ans = min(ans, cans);
vis[cent] = 1, vis_col[id[cent]] = 1;
for(auto it : adj[cent]){
if(!vis[it]) decompose(it, u);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
for(int i = 0, u, v; i < n - 1; ++i){
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1, x; i <= n; ++i){
cin >> x; id[i] = x;
col[x].push_back(i);
}
decompose();
cout << --ans << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 2e5 + 100;
vector<int> adj[mxN], col[mxN];
int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], n, k, ans = mxN;
void dfs(int u, int par){
parent[u] = par;
for(auto it : adj[u]){
if(!vis[it] && it ^ par && !vis_col[id[it]]) dfs(it, u);
}
}
void calc_sz(int u, int par){
sz[u] = 1;
for(auto it : adj[u]){
if(!vis[it] && it ^ par && !vis_col[id[it]]){
calc_sz(it, u);
sz[u] += sz[it];
}
}
}
int find_cent(int u, int par, int nby2){
for(auto it : adj[u]){
if(!vis[it] && it ^ par && !vis_col[id[it]] && sz[it] >= nby2){
return find_cent(it, u, nby2);
}
}
return u;
}
void decompose(int u = 1, int par = -1){
calc_sz(u, -1);
int cent = find_cent(u, -1, sz[u] / 2);
dfs(cent, -1);
queue<int> q;
q.push(id[cent]);
vector<int> cvis(k + 1, 0);
int cans = 0;
while(q.size()){
auto tp = q.front();
q.pop();
if(cvis[tp]) continue;
cvis[tp] = 1;
cans += 1;
for(auto it : col[tp]){
if(parent[it] != -1){
if(vis_col[id[parent[it]]]){
cans = mxN;
break;
}
if(!cvis[id[parent[it]]]){
q.push(id[parent[it]]);
//cvis[id[parent[it]]] = 1;
}
}
}
}
ans = min(ans, cans);
vis[cent] = 1, vis_col[id[cent]] = 1;
for(auto it : adj[cent]){
if(!vis[it]) decompose(it, u);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
for(int i = 0, u, v; i < n - 1; ++i){
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1, x; i <= n; ++i){
cin >> x; id[i] = x;
col[x].push_back(i);
}
decompose();
cout << --ans << "\n";
return 0;
}