# 某島

… : "…アッカリ～ン . .. . " .. .
July 16, 2015

## BZOJ 1912. [Apio2010]patrol 巡邏

```
const int N = int(1e5) + 9, M = N*2;

int hd[N], suc[M], to[M], ww[M/2];
int f1[N], f2[N], p1[N], p2[N], n, K;

#define bb to[i]
#define aa to[i^1]
#define w ww[i/2]
#define v bb

void dfs(int u = 1, int p = 0){
f1[u] = f2[u] = 0;
p1[u] = p2[u] = 0;

REP_G(i, u) if (v != p){
dfs(v, u); int t = f1[v] + w;
if (t > f1[u]){
f2[u] = f1[u];
f1[u] = t;
p2[u] = p1[u];
p1[u] = i;
}
else if (t > f2[u]){
f2[u] = t;
p2[u] = i;
}
}
}

int get_diameter(){
dfs();
int r = 1; FOR_1(i, 2, n) if (f1[i]+f2[i] > f1[r]+f2[r]) r = i;
for (int i=p1[r];i;w=-w,i=p1[bb]);
for (int i=p2[r];i;w=-w,i=p1[bb]);
return f1[r]+f2[r];
}

int main(){

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif

RD(n, K); for (int i=2;i<n*2;){
RD(aa, bb); w = 1;
suc[i] = hd[aa], hd[aa] = i, ++i;
suc[i] = hd[aa], hd[aa] = i, ++i;
}
int z = 2*(n-1);
DO(K) z -= get_diameter() - 1;
cout << z << endl;
}

```