This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
vector<int> adj[MAX];
int col[MAX];
int prt[MAX];
int num[MAX];
int vis[MAX];
int C[MAX];
int used[MAX];
int cvis[MAX];
void make_num(int x, int c, int p = 0) {
col[x] = c;
num[x] = 1;
for (auto v : adj[x]) {
if (col[v] == c) continue;
if (vis[v]) continue;
make_num(v, c, x);
num[x] += num[v];
}
}
void dfs(int x, int c, int p = 0) {
prt[x] = p;
used[x] = 0;
for (auto v : adj[x]) {
if (col[v] != c) continue;
if (v == p) continue;
if (vis[v]) continue;
dfs(v, c, x);
}
}
int cnt, ans, N, K;
vector<int> cs[MAX];
void make_tree(int x) {
cnt++;
make_num(x, cnt);
int c = x;
int n = num[x];
while (1) {
int changed = 0;
for (auto v : adj[c]) {
if (vis[v]) continue;
if (num[c] < num[v]) continue;
if (num[v] > n / 2) {
changed = 1;
c = v;
break;
}
}
if (!changed) break;
}
vector<int> all;
queue<int> q;
int sum = 0;
dfs(c, cnt);
q.push(C[c]);
int pos = 1;
used[c] = 1;
while (q.size()) {
int c = q.front();
q.pop();
if (cvis[c]) continue;
cvis[c] = 1;
all.push_back(c);
sum++;
for (auto v : cs[c]) {
if (col[v] != cnt) {
pos = 0;
break;
}
while (1) {
if (used[v]) break;
q.push(C[v]);
used[v] = 1;
v = prt[v];
}
}
if (!pos) break;
}
for (auto v : all) cvis[v] = 0;
if (pos) ans = min(ans, sum);
vis[c] = 1;
for (auto v : adj[c]) if (!vis[v]) make_tree(v);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, K;
cin >> N >> K;
ans = N;
int i, a, b;
for (i = 1; i < N; i++) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (i = 1; i <= N; i++) cin >> C[i], cs[C[i]].push_back(i);
make_tree(1);
cout << ans - 1 << ln;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |