#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
const int N = (int)5e5+10;
int n, k;
vector<int> adj[N];
int p[N], sz[N];
int a[N], tot[N], deg[N];
map<int,int> S[N];
int findSet(int i){return i==p[i]?i:p[i]=findSet(p[i]);}
void unionSet(int i, int j){
int x = findSet(i), y = findSet(j);
if(x==y) return;
if(sz[x]<sz[y])swap(x,y);
p[y] = x, sz[x]+=sz[y];
}
void dfs(int s, int p){
S[s][a[s]]=1;
if(S[s][a[s]]==tot[a[s]])
S[s].erase(S[s].find(a[s]));
for(auto u : adj[s]){
if(u==p) continue;
dfs(u,s);
if(sz(S[s]) < sz(S[u])) S[s].swap(S[u]);
for(auto [v,w] : S[u]){
S[s][v]+=w;
if(S[s][v]==tot[v])
S[s].erase(S[s].find(v));
}
}
if(p and !sz(S[s])) deg[s]++,deg[p]++;
}
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) p[i]=i,sz[i]=1;
for(int i = 1; i < n; i++){
int a, b; cin >> a >> b;
adj[a].pb(b); adj[b].pb(a);
}
for(int i = 1; i <= n; i++)
cin >> a[i], tot[a[i]]++;
dfs(1,0);
for(int i = 1; i <= n; i++)
for(int j : adj[i])
if(findSet(i)!=findSet(j))
deg[findSet(i)]++;
int cnt = 1;
for(int i = 1; i <= n; i++) cnt+=(deg[i]==1);
cout << cnt/2 << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
35920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
35920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
35920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
45508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
35920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
