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;
}

Posted by xiaodao
Category: BZOJ