LOJ3280

Solution

先考虑O(n2)O(n^2)暴力: 把颜色看成点,若颜色xx的虚树内存在颜色yy,则连边yxy \rightarrow x。然后跑tarjan缩点,新图中入度为00的点的size1size - 1的最小值即为答案

考虑优化,有很多种做法:

  1. 直接倍增优化建边

  2. 考虑点分治,在分治中心为xx时处理把所有颜色变为AxA_x的答案。暴力扩展颜色,只要存在某个先决条件颜色,满足该颜色存在一个不在当前分治联通块内的点,那么把所有颜色变为AxA_x这种方案是不优的,直接停止

我写的是做法2

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e5;

int N, K, A[MAXN + 5];
vector <int> G[MAXN + 5], col[MAXN + 5];
int ans = INT_MAX;

namespace DIV
{
int o, mn;
int Vis[MAXN + 5], size[MAXN + 5];

inline void dfs_size (int x, int f)
{
size[x] = 1;
for (int y : G[x]) if (y != f && !Vis[y])
{
dfs_size (y, x);
size[x] += size[y];
}
}

inline void dfs_root (int x, int f, int all)
{
int mx = all - size[x];
for (int y : G[x]) if (y != f && !Vis[y])
{
dfs_root (y, x, all);
Chkmax (mx, size[y]);
}
if (Chkmin (mn, mx)) o = x;
}

int is_key[MAXN + 5], fa[MAXN + 5];

inline void dfs_ins (int x, int f)
{
fa[x] = f;
is_key[x] = 1;
for (int y : G[x]) if (y != f && !Vis[y]) dfs_ins (y, x);
}

inline void dfs_del (int x, int f)
{
is_key[x] = 0;
for (int y : G[x]) if (y != f && !Vis[y]) dfs_del (y, x);
}

inline void calc (int o)
{
dfs_ins (o, 0);

static vector <int> stk; stk.clear();
static int in_stk[MAXN + 5];

static queue <int> Q; while (!Q.empty()) Q.pop();
Q.push (A[o]); stk.pb (A[o]), in_stk[A[o]] = 1;

while (!Q.empty())
{
int x = Q.front(); Q.pop();
for (int p : col[x])
{
if (!is_key[p])
{
for (int i : stk) in_stk[i] = 0;
dfs_del (o, 0);
return ;
}

while (p && is_key[p] != 2)
{
is_key[p] = 2;
if (!in_stk[A[p]]) stk.pb (A[p]), in_stk[A[p]] = 1, Q.push (A[p]);
p = fa[p];
}
}
}

Chkmin (ans, (int) stk.size() - 1);

for (int i : stk) in_stk[i] = 0;
dfs_del (o, 0);
}

inline void solve (int x)
{
o = -1, mn = INT_MAX;
dfs_size (x, 0), dfs_root (x, 0, size[x]);
x = o;
// DEBUG (o);

Vis[x] = 1;
calc (x);

for (int y : G[x]) if (!Vis[y])
solve (y);
}
}

inline void Solve ()
{
DIV :: solve (1);
cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), K = read<int>();
for (int i = 1; i < N; ++i)
{
int x = read<int>(), y = read<int>();
G[x].pb (y);
G[y].pb (x);
}
for (int i = 1; i <= N; ++i)
{
A[i] = read<int>();
col[A[i]].pb (i);
}
}

int main ()
{

#ifdef hk_cnyali
freopen("capital.in", "r", stdin);
freopen("capital.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}