#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
vector<int> adj[mxN];
int n, k;
vector<int> state[mxN];
int high[mxN];
int depth[mxN];
int val[mxN];
int par[mxN][21];
bool flag[mxN];
int best[mxN];
int ans = 0;
int cnt =0;
int sub[mxN];
vector<int> subans;
int walk(int a, int b) {
uwu(lg, 21, 0) {
if(b&(1<<lg)) {
a = par[a][lg];
}
}
return a;
}
int lca(int a, int b) {
if(depth[a]<depth[b]) {
walk(b, depth[b]-depth[a]);
}else if(depth[a]>depth[b]) {
walk(a, depth[a]-depth[b]);
}
if(a==b)return a;
uwu(lg, 21, 0) {
if(par[a][lg]!=par[b][lg]) {
a = par[a][lg];
b = par[b][lg];
}
}
return par[a][0];
}
void dfs(int u, int p) {
par[u][0] = p;
for(int v: adj[u]) {
if(v==p)continue;
depth[v] =depth[u]+1;
dfs(v, u);
}
}
void solve(int u, int p) {
best[u] = depth[high[val[u]]];
//cout<<u<<" "<<best[u]<<'\n';
if(p==0&&u!=0) {
sub[u] = cnt++;
subans.senpai(0);
}else if(p!=0) {
sub[u] = sub[p];
}
for(int v: adj[u]) {
if(v==p)continue;
solve(v, u);
if(flag[v]) {
flag[u] = true;
}
best[u] = min(best[u], best[v]);
}
if(flag[u])return;
if(depth[best[u]]==depth[u]&&u!=p) {
subans[sub[u]]++;
flag[u] = true;
}
}
int main()
{
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
cin.tie(0)->sync_with_stdio(0);
cin>>n>>k;
int a, b;
owo(i, 0, n-1) {
cin>>a>>b;
a--; b--;
adj[a].senpai(b);
adj[b].senpai(a);
}
owo(i, 0, n) {
cin>>a;
a--;
val[i] = a;
state[a].senpai(i);
}
dfs(0, 0);
owo(lg, 1, 21){
owo(i, 0, n) {
par[i][lg] = par[par[i][lg-1]][lg-1];
}
}
owo(i, 0, k) {
int comlca = state[i][0];
owo(j, 1, state[i].size()) {
comlca = lca(comlca, state[i][j]);
}
high[i] = comlca;
//cout<<i<<" "<<high[i]<<"\n";
}
solve(0, 0);
int left =0;
int right = subans.size()-1;
while(left<right) {
if(subans[left]==0) {
left++;
continue;
}
if(subans[right]==0){
right--;
continue;
}
subans[left]--;
subans[right]--;
ans++;
}
ans+=subans[left];
cout<<ans<<"\n";
return 0;
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:2:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
^
mergers.cpp:113:9: note: in expansion of macro 'owo'
owo(j, 1, state[i].size()) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
37744 KB |
Output is correct |
| 2 |
Incorrect |
101 ms |
40816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
