이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
#include <functional>
using namespace std;
const int N = 2e5 + 7;
int c[N];
int allcnt[N];
vector<int> g[N];
int used[N];
int sz[N];
int fup[N];
vector<int> bc[N];
vector<int> sn;
void dfs_find(int v, int p, int nsz, int &to) {
sz[v] = 1;
int mx = -1;
for (auto t : g[v]) {
if (!used[t] && t != p) {
dfs_find(t, v, nsz, to);
mx = max(mx, sz[t]);
sz[v] += sz[t];
}
}
mx = max(mx, nsz - sz[v]);
if (2 * mx <= nsz) {
to = v;
}
}
void dfs_sz(int v, int p) {
sz[v] = 1;
for (auto t : g[v]) {
if (!used[t] && t != p) {
dfs_sz(t, v);
sz[v] += sz[t];
}
}
}
void dfs_init(int cur, int p) {
sn.push_back(cur);
bc[c[cur]].push_back(cur);
for (auto t : g[cur]) {
if (!used[t] && t != p) {
if (c[cur] == c[t]) {
fup[t] = fup[cur];
} else {
fup[t] = cur;
}
dfs_init(t, cur);
}
}
}
int cans = 0;
int tk[N];
void set_tk(int v) {
if (tk[c[v]]) return;
tk[c[v]] = 1;
cans++;
if ((int)bc[c[v]].size() < allcnt[c[v]]) {
cans += N;
}
for (auto ov : bc[c[v]]) {
if (fup[ov] != -1) {
set_tk(fup[ov]);
}
}
}
void dfs_centr(int v, int nsz, int &rans) {
int cen = -1;
dfs_find(v, -1, nsz, cen);
assert(cen != -1);
used[cen] = 1;
sn.clear();
dfs_sz(cen, -1);
fup[cen] = -1;
dfs_init(cen, -1);
cans = 0;
set_tk(cen);
rans = min(rans, cans);
for (auto t : sn) {
tk[c[t]] = 0;
bc[c[t]].clear();
}
for (auto t : g[cen]) {
if (used[t]) continue;
dfs_centr(t, sz[t], rans);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i + 1 < n; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i < n; i++) {
cin >> c[i];
allcnt[c[i]]++;
}
int ans = n;
dfs_centr(0, n, ans);
cout << ans - 1 << endl;
}
# | 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... |