//もう布団の中から出たくない
//布団の外は寒すぎるから
//布団の中から出たくない
//布団の中はあたたかすぎるから
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,k;
vector<int> al[200005];
int arr[200005];
vector<int> pos[200005];
int pp[200005];
void dfs(int i,int p){
pp[i]=p;
for (auto it:al[i]){
if (it==p) continue;
dfs(it,i);
}
}
bool vis[200005];
bool vis2[200005];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>k;
int a,b;
rep(x,1,n){
cin>>a>>b;
al[a].pub(b);
al[b].pub(a);
}
rep(x,1,n+1) cin>>arr[x];
rep(x,1,n+1) pos[arr[x]].pub(x);
int ans=1e9;
rep(x,1,n+1){
dfs(x,-1);
rep(x,1,n+1) vis[x]=vis2[x]=false;
vis[x]=true;
vector<int> stk={x};
int curr=0;
while (!stk.empty()){
int u=stk.back(); stk.pob();
if (!vis2[arr[u]]){
vis2[arr[u]]=true;
curr++;
for (auto it:pos[arr[u]]) if (!vis[it]){
vis[it]=true;
stk.pub(it);
}
}
if (pp[u]!=-1 && !vis[pp[u]]){
vis[pp[u]]=true;
stk.pub(pp[u]);
}
}
//cout<<x<<" "<<curr<<endl;
ans=min(ans,curr);
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3072 ms |
33900 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
