#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; vi graph[500001]; int color[500001]; int precolor[500001]; int pre[500001]; int cur_pre; bool block[500001]; bool odw[500001]; int P[500001]; vi ls; int cnt = 0; void dfs_pre(int v, int pop) { P[v] = pop; ls.pb(v); pre[v] = cur_pre++; forall(it,graph[v]) { if(it != pop) { dfs_pre(it,v); } } } int dfs_block(int v, int pop) { int min_ = precolor[color[v]]; forall(it,graph[v]) { if(it != pop) { min_ = min(min_,dfs_block(it,v)); } } if(min_ == pre[v] && pop != v) block[v] = 1; return min_; } void dfs_ans(int v, int pop) { if(block[v]) { cnt++; if(v != pop) return; } odw[v] = 1; forall(it,graph[v]) { if(it != P[v]) dfs_ans(it,v); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,k; cin >> n >> k; rep2(i,1,k) precolor[i] = 1e9; rep(i,n-1) { int a,b; cin >> a >> b; graph[a].pb(b); graph[b].pb(a); } dfs_pre(1,1); rep2(i,1,n) cin >> color[i]; rep2(i,1,n) precolor[color[i]] = min(precolor[color[i]],pre[i]); dfs_block(1,1); int ans = 0; forall(it,ls) { if(odw[it]) continue; cnt = 0; dfs_ans(it,it); if(cnt <= 1) ans++; } cout << ans-1 << "\n"; }