#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 100005;
vector<int> g[N], G[N], state[N];
int p[N], parent[N], target[N], level[N], LCA[20][N], dp[N][3];
int n, ans, tmp[3];
int fin(int i){
if(p[i] == i) return i;
return p[i] = fin(p[i]);
}
void dfs(int u, int v){
LCA[0][u] = v;
level[u] = level[v] + 1;
parent[u] = v;
for(int e : g[u]){
if(e == v) continue;
dfs(e, u);
}
}
void DFS(int u, int v){
/*printf("==%d\n",u);*/
int leaf = 1;
dp[u][0] = 0;
dp[u][1] = dp[u][2] = N;
int i,j,k;
for(int e : G[u]){
if(e == v) continue;
leaf = 0;
DFS(e, u);
for(i=0;i<3;i++) tmp[i] = N;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
for(k=1;k<3;k++){
if(j+k<i) continue;
tmp[i] = min(tmp[i], dp[u][j]+dp[e][k]-min((j+k-i)/2,min(j,k)));
}
}
}
/*printf("**##%d : %d %d %d\n",u,tmp[0],tmp[1],tmp[2]);*/
for(i=0;i<3;i++) dp[u][i] = tmp[i];
}
if(leaf){
dp[u][0] = 0;
dp[u][1] = 1;
dp[u][2] = N;
}
/*printf("#%d : %d %d %d\n",u,dp[u][0],dp[u][1],dp[u][2]);*/
return ;
}
int getLCA(int a, int b){
if(level[a] < level[b]) swap(a, b);
int i;
for(i = 16; i >= 0; i--){
if(level[LCA[i][a]] >= level[b]) a = LCA[i][a];
}
/*printf("sddsas %d %d\n",a,b);*/
if(a == b) return a;
for(i = 16; i >= 0; i--){
if(LCA[i][a] != LCA[i][b]) a = LCA[i][a], b = LCA[i][b];
}
return LCA[0][a];
}
int main(){
int i,j,k,l,a,b,c,d;
scanf("%d%d",&n,&k);
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
g[a].pb(b);
g[b].pb(a);
}
for(i=1;i<=n;i++){
scanf("%d",&a), p[i]=i;
state[a].pb(i);
}
dfs(1, 0);
for(i = 1; i < 17; i++){
for(j = 1; j <= n; j++){
LCA[i][j] = LCA[i-1][LCA[i-1][j]];
}
}
/*for(i=1;i<=n;i++) printf("%d : %d %d %d\n",i,level[i],LCA[0][i],LCA[1][i]);*/
for(i = 1; i <= k; i++){
target[i] = state[i][0];
for(j = 1; j < SZ(state[i]); j++){
/*printf("%d %d",target[i],state[i][j]);*/
target[i] = getLCA(target[i], state[i][j]);
/*printf(": %d\n",target[i]);*/
}
/*printf("#%d : %d\n",i,target[i]);*/
for(int it : state[i]){
a = fin(it);
while(level[a] < level[target[i]]){
p[fin(a)] = fin(parent[a]);
a = fin(parent[a]);
}
}
}
for(i = 1; i <= n; i++){
for(int e : g[i]){
if(fin(i) != fin(e)){
G[fin(i)].pb(fin(e));
}
}
}
for(i = 1; i <= n; i++){
sort(all(G[i]));
G[i].erase(unique(all(G[i])), G[i].end());
}
DFS(1, 1);
printf("%d",dp[1][0]);
return 0;
}
/*
4 4
1 2
1 3
1 4
1 2 3 4
(2)
6 6
1 2
1 3
1 4
4 5
5 6
1 2 3 4 5 6
(2)
7 7
1 2
1 3
2 4
2 5
3 6
3 7
1 2 3 4 5 6 7
(2)
10 10
1 2
1 3
1 4
4 5
4 6
5 7
5 8
6 9
6 10
1 2 3 4 5 6 7 8 9 10
(3)
9 9
1 2
2 3
2 4
1 5
5 6
5 7
7 8
7 9
1 2 3 4 5 6 7 8 9
(3)
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4
5 4
1 2
2 3
3 4
4 5
1
2
3
4
1
2 2
1 2
1
2
*/
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:80:12: warning: unused variable 'l' [-Wunused-variable]
int i,j,k,l,a,b,c,d;
^
mergers.cpp:80:18: warning: unused variable 'c' [-Wunused-variable]
int i,j,k,l,a,b,c,d;
^
mergers.cpp:80:20: warning: unused variable 'd' [-Wunused-variable]
int i,j,k,l,a,b,c,d;
^
mergers.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
~~~~~^~~~~~~~~~~~~~
mergers.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
mergers.cpp:88:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a), p[i]=i;
~~~~~~~~~~~~~~^~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
136 ms |
25328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
