#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e5+5;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll n,m,x,y,col[N],maxn[N],vis[N],sub[N],vis_col[N],ans=INF;
vector<ll> v[N],C[N];
ll pa[N],tag[N];
ll Find_root(ll nd){
function<void(ll,ll)> DFS = [&](ll id,ll p){
sub[id]=1;maxn[id]=-1;
for(auto i:v[id]){
if(i!=p&&!vis[i]){
DFS(i,id);
sub[id]+=sub[i];
if(maxn[id]==-1||sub[maxn[id]]<sub[i])maxn[id]=i;
}
}
};
DFS(nd,0);
ll tot=sub[nd];
while(maxn[nd]!=-1&&sub[maxn[nd]]*2>=tot)nd=maxn[nd];
return nd;
}
void centroid(ll nd){
ll rt=Find_root(nd);
function<void(ll,ll)> DFS = [](ll id,ll p){
pa[id]=p;tag[id]=rt;
for(auto i:v[id]){
if(!vis[i]&&i!=p)DFS(i,id);
}
};
DFS(rt,rt);
vector<ll> res;
queue<ll> q;
q.push(rt);
ll cnt=-1,ok=1,u;
while(SZ(q)&&ok){
u=q.front();q.pop();
++cnt;
while(ok){
if(tag[u]==0)break;
if(!vis_col[col[u]]){
cnt-=SZ(C[col[u]]);
vis_col[col[u]]=1;
res.pb(col[u]);
for(auto i:C[col[u]]){
q.push(i);
if(tag[i]!=rt){
ok=0;break;
}
}
}
tag[u]=0;
u=pa[u];
if(u==rt)break;
}
}
for(auto i:res)vis_col[i]=0;
if(cnt==0)ans=min(ans,SZ(res)-1);
vis[u]=1;
for(auto i:v[u])if(!vis[i])centroid(i);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
REP1(i,n-1)cin>>x>>y,v[x].pb(y),v[y].pb(x);
REP1(i,n)cin>>col[i],C[col[i]].pb(i);
centroid(1);
cout<<ans<<"\n";
return 0;
}
Compilation message
capital_city.cpp: In lambda function:
capital_city.cpp:48:20: error: 'rt' is not captured
48 | pa[id]=p;tag[id]=rt;
| ^~
capital_city.cpp:47:31: note: the lambda has no capture-default
47 | function<void(ll,ll)> DFS = [](ll id,ll p){
| ^
capital_city.cpp:46:5: note: 'll rt' declared here
46 | ll rt=Find_root(nd);
| ^~
capital_city.cpp:50:21: error: 'DFS' is not captured
50 | if(!vis[i]&&i!=p)DFS(i,id);
| ^~~
capital_city.cpp:47:31: note: the lambda has no capture-default
47 | function<void(ll,ll)> DFS = [](ll id,ll p){
| ^
capital_city.cpp:47:24: note: 'std::function<void(long long int, long long int)> DFS' declared here
47 | function<void(ll,ll)> DFS = [](ll id,ll p){
| ^~~
