#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#warning change
const int mxN=2e5;
int n, k, c[mxN], d[mxN], anc[mxN][18], tin[mxN], t, who[20*mxN], cnt[20*mxN];
vector<int> oc[mxN], adj1[mxN], adj2[20*mxN], adj3[20*mxN], st;
bool vis[20*mxN], out[20*mxN];
void dfs1(int u=0) {
tin[u]=t++;
for (int i=1; i<18; ++i)
anc[u][i]=anc[anc[u][i-1]][i-1];
for (int v : adj1[u])
if (v!=anc[u][0]) {
d[v]=d[u]+1, anc[v][0]=u;
dfs1(v);
}
}
int lca(int u, int v) {
if (d[u]>d[v])
swap(u, v);
for (int i=17; ~i; --i)
if (d[v]-(1<<i)>=d[u])
v=anc[v][i];
if (u==v)
return u;
for (int i=17; ~i; --i)
if (anc[u][i]!=anc[v][i])
u=anc[u][i], v=anc[v][i];
return anc[u][0];
}
void dfs2(int u) {
vis[u]=1;
for (int v : adj2[u])
if (!vis[v])
dfs2(v);
st.push_back(u);
}
void dfs3(int u, int rt) {
vis[u]=0, who[u]=rt;
cnt[rt]+=u<k;
for (int v : adj3[u])
if (vis[v])
dfs3(v, rt);
}
void ae(int u, int v) {
//cout << u << " " << v << endl;
adj2[u].push_back(v);
adj3[v].push_back(u);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i=1; i<n; ++i) {
int u, v;
cin >> u >> v, --u, --v;
adj1[u].push_back(v);
adj1[v].push_back(u);
}
for (int i=0; i<n; ++i) {
cin >> c[i], --c[i];
oc[c[i]].push_back(i);
}
dfs1();
for (int i=0; i<k; ++i) {
sort(oc[i].begin(), oc[i].end(), [&](int a, int b) { return tin[a]<tin[b]; } );
for (int j=1; j<oc[i].size(); ++i) {
int u=oc[i][j-1], v=oc[i][j];
int uv=lca(u, v);
ae(i, c[uv]);
for (int rep=0; rep<2; ++rep) {
for (int j=17; ~j; --j)
if (d[u]-(1<<j)>=d[uv]) {
//cout << i << " " << u << " " << j << endl;
ae(i, j*n+u+k);
u=anc[u][j];
}
swap(u, v);
}
}
}
for (int i=0; i<n; ++i) {
ae(i+k, c[i]);
for (int j=1; j<18; ++j) {
ae(j*n+i+k, (j-1)*n+i+k);
ae(j*n+i+k, (j-1)*n+anc[i][j-1]+k);
}
}
for (int i=0; i<k; ++i)
if (!vis[i])
dfs2(i);
reverse(st.begin(), st.end());
for (int i : st)
if (vis[i])
dfs3(i, i);
for (int i : st)
for (int j : adj2[i])
if (who[i]!=who[j])
out[who[i]]=1;
//for (int i=0; i<k; ++i)
// cout << who[i] << endl;
int ans=69696969;
for (int i=0; i<k; ++i)
if (!out[who[i]])
ans=min(ans, cnt[who[i]]-1);
cout << ans;
return 0;
}
Compilation message
capital_city.cpp:7:2: warning: #warning change [-Wcpp]
7 | #warning change
| ^~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int j=1; j<oc[i].size(); ++i) {
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
197528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
197528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2731 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
197528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
