注：作者YWhgs大佬，我只是不知道怎么把文件发到团队里，我自己写完题解会替换掉
对于
20
20
20% 的数据，
n
≤
1000
n \leq 1000
n≤1000。
显然对于这一档部分分我们可以枚举每一个点
x
x
x，比较一下
1
1
1 和
x
x
x 哪个先到
i
i
i，然后取个
min
\min
min 就好了。复杂度
O
(
n
2
)
O(n^2)
O(n2)。其实还可以剪个枝，数据水，可以拿到 80 分。
对于树的数据。
考虑到一棵树 每一条树上路径的边 都是固定的，所以可以直接找 1 → x 1 \to x 1→x 的中点，如果长度为奇数，找 1 → x 1 \to x 1→x 距离 x x x 为 ⌊ d i s t a n c e ( 1 , x ) 2 ⌋ \lfloor \frac{distance(1,x)}{2} \rfloor ⌊2distance(1,x)⌋ 的那个点 y y y，答案就是 s z y sz_y szy。但是经过一番仔细思考，你会发现可以直接枚举 1 1 1 的儿子作为 y y y 就可以了，非常简单，这个直接取 n − m a x ( s z y ) n - max(sz_y) n−max(szy)。复杂度 O ( n ) O(n) O(n)。
对于 100 100 100% 的数据， n ≤ 1 0 5 n \leq 10^5 n≤105。
定义 K ( x , k ) K(x,k) K(x,k) 为 x x x 的 k k k 级祖先。
发现可以先搞出一颗 bfs 弄出来的一颗树，然后多出来的边不会超过 100 100 100 条，即多出来的点不会超过 200 200 200 个。把这 200 200 200 个点定义为 特殊点。然后非常容易想到，对这 200 200 200 个特殊点遍历整个图，求出这些点到其他点的最短距离。
然后就是在这棵树上做文章了。发现一个 特殊点 对一个点 x x x 有用，当且仅当这个点 y y y 离 x x x 的距离 d i s t a n c e x , y distance_{x,y} distancex,y小于等于 d i s t a n c e 1 , y distance_{1,y} distance1,y，然后对于这个点它能更新到的部分其实是 K ( y , ⌊ d i s t a n c e ( 1 , y ) − d i s t a n c e ( x , y ) 2 ⌋ ) K(y,\lfloor \frac{distance(1,y)-distance(x,y)}{2} \rfloor) K(y,⌊2distance(1,y)−distance(x,y)⌋) 的所有儿子。
然后对于所有的特殊点，其实是有重叠部分的，如果有重叠部分的话，那么 L y ≤ d f n y ′ ≤ R y L_y \leq dfn_y' \leq R_y Ly≤dfny′≤Ry。这个是一个经典的判 y ′ y' y′ 是否在 y y y 子树内的方法，其中 L , R L,R L,R 指的是这一个子树区间。当然你可以理解成 R i = L i + s i z e i − 1 R_i = L_i + size_i - 1 Ri=Li+sizei−1。然后就可以去排个序，扫描一下，就可以搞完了。
下面这份代码有点离谱，原意是离线下来然后去掉一个
log
\log
log 的倍增和排序的复杂度…谁知道越跑越慢。。。可能是实现比较烂。。
感觉写个长链剖分比直接离线 d f s dfs dfs 一遍求 K ( x ) K(x) K(x) 要快啊。。
warning:下面这份代码空间需求大概比较大，建议长链剖分 O(1) 求 K(x)。
复杂度 O ( n ∗ 200 ) O(n * 200) O(n∗200)。
#include <bits/stdc++.h>
void cmin(int &x, const int &y) { x = (x < y) ? x : y; }
const int N = 262144;
int n, m;
std::vector<int> g[N];
int dis[N], order[N], cnt, sz[N], par[N];
int q[N], h, t;
int special[202], nodes;
void bfs1() {
q[h = t = 1] = 1; dis[1] = 1;
while (h <= t) {
int u = q[h++]; order[++cnt] = u;
for (auto v : g[u]) {
if (!dis[v]) {
dis[v] = dis[u] + 1;
par[q[++t] = v] = u;
}
}
}
}
int dist[202][N];
void bfs(int i, int s) {
q[h = t = 1] = s; dist[i][s] = 1;
while (h <= t) {
int u = q[h++];
for (auto v : g[u]) {
if (!dist[i][v]) {
dist[i][q[++t] = v] = dist[i][u] + 1;
}
}
}
}
int L[N], R[N], Index;
void dfs(int u) {
L[u] = ++Index;
for (auto v : g[u]) {
if (par[v] == u) {
dfs(v);
}
}
R[u] = Index;
}
std::vector<std::pair<int, int> > task[N];
std::vector<int> hav[N];
void calc(int u, int k, int id) {
if (dis[u] < k) {
return;
} else {
task[u].emplace_back(dis[u] - k >> 1, id);
}
}
int stk[N], top;
void dfs2(int u) {
stk[++top] = u;
for (auto x : task[u]) {
int k = x.first;
hav[stk[top - k]].emplace_back(x.second);
}
for (auto v : g[u]) {
if (par[v] == u) {
dfs2(v);
}
}
--top;
}
std::vector<int> v[N];
void dfs3(int u) {
for (auto id : hav[u]) {
v[id].emplace_back(u);
}
for (auto v : g[u]) {
if (par[v] == u) {
dfs3(v);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
freopen("starwar.in", "r", stdin);
freopen("starwar.out", "w", stdout);
std::cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
std::cin >> x >> y;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
bfs1();
for (int i = n; i >= 1; i--) {
int u = order[i]; sz[u] = 1;
for (auto v : g[u]) {
if (par[v] == u) {
sz[u] += sz[v];
}
}
}
for (int u = 1; u <= n; u++) {
for (auto v : g[u]) {
if (v != par[u] && u != par[v]) {
special[++nodes] = u;
bfs(nodes, u);
break;
}
}
}
dfs(1);
int ans = n;
for (int i = 2; i <= n; i++) {
calc(i, 1, i);
for (int j = 1; j <= nodes; j++) {
calc(special[j], dist[j][i], i);
}
}
dfs2(1);
dfs3(1);
static int tmp[202], tmpl;
for (int i = 2; i <= n; i++) {
int res = n, t = 0;
tmpl = 0;
for (auto j : v[i]) {
tmp[tmpl++] = j;
}
while (t < tmpl) {
int now = t;
while (t < tmpl && L[tmp[now]] <= L[tmp[t]] && L[tmp[t]] <= R[tmp[now]]) {
++t;
}
res -= sz[tmp[now]];
}
cmin(ans, res);
}
std::cout << ans << "\n";
return 0;
}