This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
const ll maxn=1000005, inf=1e9;
stack <ll> st;
vector <pll> euler;
pll sp[20][maxn*2];
vector <ll> A[maxn], B[maxn];
ll c[maxn], lca[maxn], pa[maxn], r[maxn];
ll cnt, Time, num[maxn], lo[maxn], comp[maxn], sz[maxn];
void dfs(ll u)
{
lca[u]=euler.size()+1;
euler.pb({lca[u], u});
for (ll v:A[u])
{
if (v==pa[u])
continue;
pa[v]=u, dfs(v);
euler.pb({lca[u], u});
}
}
void initlca()
{
ll n=euler.size();
for (ll i=0; i<n; i++)
sp[0][i+1]=euler[i];
for (ll i=1; i<20; i++)
for (ll j=1; j+(1<<i)<=n+1; j++)
sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
}
ll LCA(ll u, ll v)
{
ll l=lca[u], r=lca[v];
if (l>r) swap(l, r);
ll j=__lg(r-l+1);
return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
}
void dfs2(ll u)
{
bool ok=1;
st.push(u);
lo[u]=num[u]=++Time;
for (ll v:B[u])
{
if (num[v]) lo[u]=min(lo[u], num[v]);
else
{
dfs2(v), lo[u]=min(lo[u], lo[v]);
if (lo[v]>num[u]) ok=0;
}
}
if (lo[u]==num[u])
{
cnt++, sz[cnt]=ok?1:inf;
while (st.top()!=u)
{
comp[st.top()]=cnt, sz[cnt]++;
num[st.top()]=inf, st.pop();
}
num[u]=inf, comp[u]=cnt, st.pop();
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, k, ans=inf; cin >> n >> k;
for (ll i=1; i<n; i++)
{
ll u, v; cin >> u >> v;
A[u].pb(v); A[v].pb(u);
}
dfs(1), initlca();
for (ll i=1; i<=n; i++)
{
cin >> c[i];
if (!r[c[i]]) r[c[i]]=i;
else r[c[i]]=LCA(r[c[i]], i);
}
for (ll i=1; i<=n; i++)
if (pa[i] && i!=r[c[i]])
B[c[i]].pb(c[pa[i]]);
for (ll i=1; i<=k; i++)
if (!num[i])
dfs2(1);
for (ll i=1; i<=cnt; i++)
ans=min(ans, sz[i]-1);
cout << ans << "\n";
}
Compilation message (stderr)
capital_city.cpp: In function 'void initlca()':
capital_city.cpp:39:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
39 | sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |