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>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int C = 70;
const int mxn = 2e5+10;
vector<int> tree[mxn];
int par[mxn][20],id[mxn][20],dep[mxn];
int to[mxn*C],nid[mxn*C],head[mxn];
int col[mxn];
int N,K;
int ppp = 0;
int wei[mxn*C];
vector<int> v[mxn];
int pt;
namespace BUILD{
void add_edge(int a,int b){
ppp++;
nid[ppp] = head[a];
head[a] = ppp;
to[ppp] = b;
return;
}
void dfs(int now){
id[now][0] = ++pt;
add_edge(id[now][0],now);
add_edge(id[now][0],par[now][0]);
for(int i = 1;i<20;i++){
id[now][i] = ++pt;
par[now][i] = par[par[now][i-1]][i-1];
add_edge(id[now][i],id[now][i-1]);
add_edge(id[now][i],id[par[now][i-1]][i-1]);
}
for(auto nxt:tree[now]){
if(nxt == par[now][0])continue;
par[nxt][0] = now;
dep[nxt] = dep[now]+1;
dfs(nxt);
}
return;
}
int LCA(int a,int b){
if(dep[a]<dep[b])swap(a,b);
int d = dep[a]-dep[b];
for(int i = 19;i>=0;i--){
if(d&(1<<i))a = par[a][i];
}
for(int i = 19;i>=0;i--){
if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
}
return (a==b?a:par[a][0]);
}
void add(int a,int d){
int now = a;
for(int i = 19;i>=0;i--){
if(d&(1<<i)){
add_edge(a,id[now][i]);
now = par[now][i];
}
}
return;
}
void GO(){
par[1][0] = 1;
dfs(1);
//cout<<"HH"<<endl;
for(int i = 1;i<=K;i++){
if(v[i].empty())continue;
int now = v[i][0];
for(auto &j:v[i]){
add_edge(j,i+N);
add_edge(i+N,j);
now = LCA(now,j);
}
//cout<<i<<":"<<endl;for(auto &j:v[i])cout<<j<<',';cout<<now<<endl;
for(auto &j:v[i]){
add(j,dep[j]-dep[now]);
}
}
return;
}
void PRINT(){
for(int i = 1;i<=pt;i++){
cout<<i<<":";
for(int eid = head[i];eid;eid = nid[eid]){
cout<<to[eid]<<',';
}cout<<endl;
}
return;
}
}
namespace SCC{
int idx[mxn*C],low[mxn*C],cnt = 0,gid[mxn*C],gcnt = 0;
vector<int> st;
int in[mxn*C],out[mxn*C];
int dp[mxn*C];
void dfs(int now){
idx[now] = low[now] = ++cnt;
st.push_back(now);
for(int eid = head[now];eid;eid = nid[eid]){
int nxt = to[eid];
if(gid[nxt])continue;
if(!idx[nxt]){
dfs(nxt);
low[now] = min(low[now],low[nxt]);
}
else low[now] = min(low[now],idx[nxt]);
}
if(idx[now] == low[now]){
gcnt++;
while(st.back() != now){
gid[st.back()] = gcnt;
st.pop_back();
}
gid[st.back()] = gcnt;
st.pop_back();
}
return;
}
void GO(){
for(int i = 1;i<=pt;i++){
if(!gid[i])dfs(i);
}
return;
}
void GETANS(){
for(int i = 1;i<=pt;i++){
dp[gid[i]]+=wei[i];
for(int eid = head[i];eid;eid = nid[eid]){
int nxt = to[eid];
if(gid[nxt] == gid[i])continue;
out[gid[i]]++;
in[gid[nxt]]++;
}
}
int re = 1e9;
for(int i = 1;i<=gcnt;i++){
if(out[i])continue;
re = min(re,dp[i]);
//cout<<"SCC:"<<i<<":"<<dp[i]<<endl;
}
cout<<re-1<<'\n';
return;
}
void PRINT(){
for(int i = 1;i<=pt;i++){
cout<<i<<":"<<gid[i]<<endl;
}
return;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>K;
for(int i = 1;i<N;i++){
int a,b;
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
for(int i = 1;i<=N;i++){
cin>>col[i];
v[col[i]].push_back(i);
}
for(int i = 1;i<=K;i++)wei[i+N] = 1;
pt = N+K;
//cout<<"HI"<<endl;
BUILD::GO();
if(N>=2000)return 0;
//BUILD::PRINT();
//cout<<"HI"<<endl;
SCC::GO();
//cout<<"HI"<<endl;
//SCC::PRINT();
SCC::GETANS();
}
# | 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... |