이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// meow cat, please meow back =^_^=
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
struct scc
{
int n;
vector<vector<int>> adj, adj_rev;
vector<bool> used, in;
vector<int> order, component, cnt;
void dfs1(int v) {
used[v] = true;
for (auto u : adj[v])
if (!used[u])
dfs1(u);
order.push_back(v);
}
void dfs2(int v) {
used[v] = true;
component.push_back(v);
for (auto u : adj_rev[v])
if (!used[u])
dfs2(u);
}
void add(int u, int v)
{
//cout << u << " " << v << "\n";
adj[u].push_back(v);
adj_rev[v].push_back(u);
}
void init(int m)
{
adj.assign(m, {}), adj_rev.assign(m, {}), used.assign(m, false), in.assign(m, false), cnt.assign(m, 0), order.clear(), component.clear();
n = m;
}
int solve()
{
used.assign(n, false);
for (int i = 0; i < n; i++)
if (!used[i])
dfs1(i);
used.assign(n, false);
reverse(order.begin(), order.end());
int ans = n;
for (auto v : order)
if (!used[v]) {
dfs2(v);
bool okay = true; int c = 0;
for (int i : component) in[i] = true;
for (int i : component)
{
if (cnt[i]) c++;
for (int j : adj[i]) if (!in[j]) okay = false;
}
for (int i : component) in[i] = false;
if (c && okay)
ans = min(ans, c - 1);
component.clear();
}
return ans;
}
};
const int logn = 20;
//const int logn = 4;
vector<vector<int> > g, l, col;
vector<int> d, c;
void dfs(int u)
{
for (int j = 1; j < logn; j++) l[j][u] = l[j - 1][l[j - 1][u]];
for (int v : g[u]) if (v != l[0][u]) d[v] = d[u] + 1, l[0][v] = u, dfs(v);
}
int lca(int u, int v)
{
if (d[u] < d[v]) swap(u, v);
for (int i = logn - 1; i >= 0; i--) if (d[l[i][u]] >= d[v]) u = l[i][u];
for (int i = logn - 1; i >= 0; i--) if (l[i][u] != l[i][v]) u = l[i][u], v = l[i][v];
return u == v ? u : l[0][u];
}
int n, k;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
g.assign(n, {}), l.assign(logn, vector<int>(n, 0)), d.assign(n, 0), col.assign(k, {}), c.assign(n, -1);
for (int i = 0, a, b; i < n - 1; i++) cin >> a >> b, g[--a].push_back(--b), g[b].push_back(a);
for (int i = 0; i < n; i++)
{
cin >> c[i];
col[--c[i]].push_back(i);
}
dfs(0);
scc s;
s.init(k + logn * n);
for (int i = 0; i < n; i++)
{
s.add(k + i, c[i]);
for (int b = 1; b < logn; b++) s.add(k + n * b + i, k + n * (b - 1) + i), s.add(k + n * b + i, k + n * (b - 1) + l[b - 1][i]);
}
for (int i = 0; i < k; i++)
{
s.cnt[i] = 1;
int lc = col[i][0];
for (int j : col[i]) lc = lca(lc, j);
s.add(i, k + lc);
for (int j : col[i])
{
for (int b = logn - 1; b >= 0; b--) if (d[l[b][j]] >= d[lc])
s.add(i, k + b * n + j), j = l[b][j];
}
}
cout << s.solve() << "\n";
return 0;
}
# | 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... |