#include <bits/stdc++.h>
using namespace std ;
const int MAX = 2e5 + 10 ;
int arr[MAX] ;
int n , k ;
vector< vector<int> >adj(MAX) ;
int dep[MAX] , P[MAX][20] ;
void dfs(int node , int par)
{
P[node][0] = par ;
for(int i = 1 ; i < 20 ; ++i)
P[node][i] = P[P[node][i-1]][i-1] ;
for(auto &child : adj[node])
{
if(child == par)
continue ;
dep[child] = dep[node] + 1 ;
dfs(child , node) ;
}
}
int LCA(int x , int y)
{
if(dep[x] < dep[y])
swap(x , y) ;
for(int i = 19 ; i >= 0 ; --i)
{
if(dep[x] - (1 << i) >= dep[y])
x = P[x][i] ;
}
if(x == y)
return x ;
for(int i = 19 ; i >= 0 ; --i)
{
if(P[x][i] != P[y][i])
x = P[x][i] , y = P[y][i] ;
}
return P[x][0] ;
}
int lca[MAX] ;
vector< vector<int> >adj2(MAX) , adj2R(MAX) ;
int vis[MAX] ;
vector<int>topo ;
void dfs2(int node)
{
vis[node] = 1 ;
for(auto &child : adj2[node])
{
if(vis[child])
continue ;
dfs2(child) ;
}
topo.push_back(node) ;
}
bool flag ;
int comp[MAX] , curcmp ;
int cnt ;
vector<int>v ;
void dfs2_rev(int node)
{
vis[node] = 1 , comp[node] = curcmp , cnt++ ;
v.push_back(node) ;
for(auto &child : adj2R[node])
{
if(vis[child])
continue ;
dfs2_rev(child) ;
}
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>k ;
for(int i = 0 ; i < n-1 ; ++i)
{
int x , y ;
cin>>x>>y ;
adj[x].push_back(y) ;
adj[y].push_back(x) ;
}
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
dfs(1 , -1) ;
for(int i = 1 ; i <= n ; ++i)
{
if(!lca[arr[i]])
lca[arr[i]] = i ;
else
lca[arr[i]] = LCA(lca[arr[i]] , i) ;
}
for(int i = 2 ; i <= n ; ++i)
{
if(arr[P[i][0]] != arr[i] && lca[arr[i]] != i)
adj2[arr[i]].push_back(arr[P[i][0]]) , adj2R[arr[P[i][0]]].push_back(arr[i]) ;
}
for(int i = 1 ; i <= k ; ++i)
{
if(!vis[i])
dfs2(i) ;
}
memset(vis , 0 , sizeof(vis)) ;
reverse(topo.begin() , topo.end()) ;
int ans = n ;
for(auto &node : topo)
{
if(vis[node])
continue ;
v.clear() ;
flag = true , cnt = 0 , curcmp++ ;
dfs2_rev(node) ;
for(auto &node2 : v)
{
for(auto &child : adj2[node2])
flag &= (comp[child] == curcmp) ;
}
if(flag)
ans = min(ans , cnt-1) ;
}
return cout<<ans<<"\n" , 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
15188 KB |
Output is correct |
2 |
Correct |
7 ms |
15232 KB |
Output is correct |
3 |
Correct |
7 ms |
15144 KB |
Output is correct |
4 |
Correct |
7 ms |
15188 KB |
Output is correct |
5 |
Correct |
7 ms |
15188 KB |
Output is correct |
6 |
Correct |
7 ms |
15188 KB |
Output is correct |
7 |
Correct |
7 ms |
15188 KB |
Output is correct |
8 |
Correct |
7 ms |
15188 KB |
Output is correct |
9 |
Correct |
7 ms |
15188 KB |
Output is correct |
10 |
Correct |
7 ms |
15188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
15188 KB |
Output is correct |
2 |
Correct |
7 ms |
15232 KB |
Output is correct |
3 |
Correct |
7 ms |
15144 KB |
Output is correct |
4 |
Correct |
7 ms |
15188 KB |
Output is correct |
5 |
Correct |
7 ms |
15188 KB |
Output is correct |
6 |
Correct |
7 ms |
15188 KB |
Output is correct |
7 |
Correct |
7 ms |
15188 KB |
Output is correct |
8 |
Correct |
7 ms |
15188 KB |
Output is correct |
9 |
Correct |
7 ms |
15188 KB |
Output is correct |
10 |
Correct |
7 ms |
15188 KB |
Output is correct |
11 |
Correct |
7 ms |
15444 KB |
Output is correct |
12 |
Correct |
9 ms |
15444 KB |
Output is correct |
13 |
Correct |
8 ms |
15444 KB |
Output is correct |
14 |
Correct |
8 ms |
15444 KB |
Output is correct |
15 |
Correct |
8 ms |
15572 KB |
Output is correct |
16 |
Correct |
8 ms |
15444 KB |
Output is correct |
17 |
Correct |
8 ms |
15572 KB |
Output is correct |
18 |
Correct |
8 ms |
15572 KB |
Output is correct |
19 |
Correct |
8 ms |
15484 KB |
Output is correct |
20 |
Correct |
8 ms |
15572 KB |
Output is correct |
21 |
Correct |
7 ms |
15572 KB |
Output is correct |
22 |
Correct |
8 ms |
15612 KB |
Output is correct |
23 |
Correct |
8 ms |
15572 KB |
Output is correct |
24 |
Correct |
8 ms |
15572 KB |
Output is correct |
25 |
Correct |
9 ms |
15572 KB |
Output is correct |
26 |
Correct |
9 ms |
15572 KB |
Output is correct |
27 |
Correct |
8 ms |
15572 KB |
Output is correct |
28 |
Correct |
8 ms |
15572 KB |
Output is correct |
29 |
Correct |
8 ms |
15572 KB |
Output is correct |
30 |
Correct |
8 ms |
15572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
62020 KB |
Output is correct |
2 |
Correct |
107 ms |
62504 KB |
Output is correct |
3 |
Correct |
271 ms |
61764 KB |
Output is correct |
4 |
Correct |
101 ms |
62404 KB |
Output is correct |
5 |
Correct |
222 ms |
58924 KB |
Output is correct |
6 |
Correct |
126 ms |
62284 KB |
Output is correct |
7 |
Correct |
232 ms |
58852 KB |
Output is correct |
8 |
Correct |
100 ms |
61124 KB |
Output is correct |
9 |
Correct |
211 ms |
56236 KB |
Output is correct |
10 |
Correct |
195 ms |
54168 KB |
Output is correct |
11 |
Correct |
204 ms |
56392 KB |
Output is correct |
12 |
Correct |
207 ms |
58496 KB |
Output is correct |
13 |
Correct |
202 ms |
53836 KB |
Output is correct |
14 |
Correct |
206 ms |
58832 KB |
Output is correct |
15 |
Correct |
207 ms |
58568 KB |
Output is correct |
16 |
Correct |
194 ms |
54560 KB |
Output is correct |
17 |
Correct |
195 ms |
55088 KB |
Output is correct |
18 |
Correct |
206 ms |
55240 KB |
Output is correct |
19 |
Correct |
206 ms |
57720 KB |
Output is correct |
20 |
Correct |
228 ms |
59488 KB |
Output is correct |
21 |
Correct |
7 ms |
15188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
15188 KB |
Output is correct |
2 |
Correct |
7 ms |
15232 KB |
Output is correct |
3 |
Correct |
7 ms |
15144 KB |
Output is correct |
4 |
Correct |
7 ms |
15188 KB |
Output is correct |
5 |
Correct |
7 ms |
15188 KB |
Output is correct |
6 |
Correct |
7 ms |
15188 KB |
Output is correct |
7 |
Correct |
7 ms |
15188 KB |
Output is correct |
8 |
Correct |
7 ms |
15188 KB |
Output is correct |
9 |
Correct |
7 ms |
15188 KB |
Output is correct |
10 |
Correct |
7 ms |
15188 KB |
Output is correct |
11 |
Correct |
7 ms |
15444 KB |
Output is correct |
12 |
Correct |
9 ms |
15444 KB |
Output is correct |
13 |
Correct |
8 ms |
15444 KB |
Output is correct |
14 |
Correct |
8 ms |
15444 KB |
Output is correct |
15 |
Correct |
8 ms |
15572 KB |
Output is correct |
16 |
Correct |
8 ms |
15444 KB |
Output is correct |
17 |
Correct |
8 ms |
15572 KB |
Output is correct |
18 |
Correct |
8 ms |
15572 KB |
Output is correct |
19 |
Correct |
8 ms |
15484 KB |
Output is correct |
20 |
Correct |
8 ms |
15572 KB |
Output is correct |
21 |
Correct |
7 ms |
15572 KB |
Output is correct |
22 |
Correct |
8 ms |
15612 KB |
Output is correct |
23 |
Correct |
8 ms |
15572 KB |
Output is correct |
24 |
Correct |
8 ms |
15572 KB |
Output is correct |
25 |
Correct |
9 ms |
15572 KB |
Output is correct |
26 |
Correct |
9 ms |
15572 KB |
Output is correct |
27 |
Correct |
8 ms |
15572 KB |
Output is correct |
28 |
Correct |
8 ms |
15572 KB |
Output is correct |
29 |
Correct |
8 ms |
15572 KB |
Output is correct |
30 |
Correct |
8 ms |
15572 KB |
Output is correct |
31 |
Correct |
248 ms |
62020 KB |
Output is correct |
32 |
Correct |
107 ms |
62504 KB |
Output is correct |
33 |
Correct |
271 ms |
61764 KB |
Output is correct |
34 |
Correct |
101 ms |
62404 KB |
Output is correct |
35 |
Correct |
222 ms |
58924 KB |
Output is correct |
36 |
Correct |
126 ms |
62284 KB |
Output is correct |
37 |
Correct |
232 ms |
58852 KB |
Output is correct |
38 |
Correct |
100 ms |
61124 KB |
Output is correct |
39 |
Correct |
211 ms |
56236 KB |
Output is correct |
40 |
Correct |
195 ms |
54168 KB |
Output is correct |
41 |
Correct |
204 ms |
56392 KB |
Output is correct |
42 |
Correct |
207 ms |
58496 KB |
Output is correct |
43 |
Correct |
202 ms |
53836 KB |
Output is correct |
44 |
Correct |
206 ms |
58832 KB |
Output is correct |
45 |
Correct |
207 ms |
58568 KB |
Output is correct |
46 |
Correct |
194 ms |
54560 KB |
Output is correct |
47 |
Correct |
195 ms |
55088 KB |
Output is correct |
48 |
Correct |
206 ms |
55240 KB |
Output is correct |
49 |
Correct |
206 ms |
57720 KB |
Output is correct |
50 |
Correct |
228 ms |
59488 KB |
Output is correct |
51 |
Correct |
7 ms |
15188 KB |
Output is correct |
52 |
Correct |
177 ms |
46540 KB |
Output is correct |
53 |
Correct |
160 ms |
46584 KB |
Output is correct |
54 |
Correct |
187 ms |
46564 KB |
Output is correct |
55 |
Correct |
158 ms |
46596 KB |
Output is correct |
56 |
Correct |
165 ms |
46544 KB |
Output is correct |
57 |
Correct |
167 ms |
46540 KB |
Output is correct |
58 |
Correct |
197 ms |
50048 KB |
Output is correct |
59 |
Correct |
221 ms |
50700 KB |
Output is correct |
60 |
Correct |
220 ms |
49492 KB |
Output is correct |
61 |
Correct |
205 ms |
49260 KB |
Output is correct |
62 |
Correct |
98 ms |
62332 KB |
Output is correct |
63 |
Correct |
98 ms |
62368 KB |
Output is correct |
64 |
Correct |
98 ms |
61404 KB |
Output is correct |
65 |
Correct |
102 ms |
62316 KB |
Output is correct |
66 |
Correct |
167 ms |
51780 KB |
Output is correct |
67 |
Correct |
159 ms |
51692 KB |
Output is correct |
68 |
Correct |
183 ms |
51776 KB |
Output is correct |
69 |
Correct |
179 ms |
51892 KB |
Output is correct |
70 |
Correct |
164 ms |
51724 KB |
Output is correct |
71 |
Correct |
166 ms |
51780 KB |
Output is correct |
72 |
Correct |
164 ms |
51700 KB |
Output is correct |
73 |
Correct |
162 ms |
51100 KB |
Output is correct |
74 |
Correct |
177 ms |
51872 KB |
Output is correct |
75 |
Correct |
163 ms |
51792 KB |
Output is correct |
76 |
Correct |
193 ms |
54388 KB |
Output is correct |
77 |
Correct |
190 ms |
52876 KB |
Output is correct |
78 |
Correct |
218 ms |
54976 KB |
Output is correct |
79 |
Correct |
212 ms |
53320 KB |
Output is correct |
80 |
Correct |
218 ms |
59044 KB |
Output is correct |
81 |
Correct |
207 ms |
56292 KB |
Output is correct |
82 |
Correct |
219 ms |
56376 KB |
Output is correct |
83 |
Correct |
210 ms |
53644 KB |
Output is correct |
84 |
Correct |
205 ms |
58352 KB |
Output is correct |
85 |
Correct |
202 ms |
57032 KB |
Output is correct |
86 |
Correct |
209 ms |
53308 KB |
Output is correct |
87 |
Correct |
223 ms |
54776 KB |
Output is correct |
88 |
Correct |
218 ms |
55192 KB |
Output is correct |
89 |
Correct |
215 ms |
51944 KB |
Output is correct |
90 |
Correct |
198 ms |
51872 KB |
Output is correct |
91 |
Correct |
225 ms |
53740 KB |
Output is correct |
92 |
Correct |
202 ms |
52604 KB |
Output is correct |
93 |
Correct |
232 ms |
52360 KB |
Output is correct |
94 |
Correct |
205 ms |
51824 KB |
Output is correct |
95 |
Correct |
196 ms |
53068 KB |
Output is correct |
96 |
Correct |
206 ms |
52168 KB |
Output is correct |
97 |
Correct |
213 ms |
53640 KB |
Output is correct |