/*raghav0307 - Raghav Gupta*/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define int ll
const int MAXN = 5e5 + 5;
vector<int> graph[MAXN];
vector<int> state[MAXN];
int depth[MAXN];
int parent[MAXN];
int degree[MAXN];
void dfs(int nd, int p, int lvl){
parent[nd] = p;
depth[nd] = lvl;
for(auto x: graph[nd]){
if(x == p) continue;
dfs(x, nd, lvl+1);
}
}
int color[MAXN];
int find(int x){
return color[x] == x ? x : color[x] = find(color[x]);
}
void Union(int a, int b){
if(a == b) return;
a = find(a);
b = find(b);
while(a != b){
if(depth[b] > depth[a])
swap(a, b);
int x = find(parent[a]);
color[a] = x;
a = x;
}
}
signed main(){
fast_io();
int n, k;
cin >> n >> k;
for(int i = 0; i < n-1; i++){
int a, b;
cin >> a >> b;
graph[a].pb(b);
graph[b].pb(a);
}
for(int i = 1; i <= n; i++){
int indx; cin >> indx;
state[indx].pb(i);
}
dfs(1, -1, 0);
for(int i = 1; i <= n; i++) color[i] = i;
for(int i = 1; i <= k; i++){
for(int j = 1; j < state[i].size(); j++){
Union(state[i][j], state[i][j-1]);
}
}
for(int i = 1; i <= n; i++){
for(auto x: graph[i]){
if(find(i) == find(x)) continue;
degree[find(i)]++;
}
}
int ans = 0;
for(int i = 1; i <= k; i++){
if(degree[i] == 1) ans++;
}
cout << (ans+1)/2 << "\n";
return 0;
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1; j < state[i].size(); j++){
~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23888 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 8 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 9 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
25 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 12 |
Incorrect |
23 ms |
23808 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23888 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 8 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 9 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
25 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 12 |
Incorrect |
23 ms |
23808 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23888 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 8 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 9 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
25 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 12 |
Incorrect |
23 ms |
23808 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
86 ms |
32640 KB |
Output is correct |
| 2 |
Correct |
96 ms |
35820 KB |
Output is correct |
| 3 |
Incorrect |
24 ms |
24192 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23888 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 8 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 9 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
25 ms |
23808 KB |
Output is correct |
| 11 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 12 |
Incorrect |
23 ms |
23808 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
