题解|算法竞赛进阶指南 巡逻

k=1时，如果我们新修建一个道路，那么就会有一段路程少走一遍。此时选择连接树的直径的两个端点显然是最优的。

难就难在k=2的时候，还是上面的思路，先连接两个直径的端点。假设我们接下来连接的是x,y两个叶子结点，它们到直径的距离分别为dis[x],dis[y]，并设直径上两点的距离为d[u,v]，这里u,v分别为x,y所在链和直径的交点。

因此最后的答案会增加d[u,v]-dis[x]-dis[y]。要使答案最小，那么也就是使dis[x]+dis[y]-d[u,v]最大。这其实就是把u到v路径上的边权取反后，树的最长链。

再求一次树的直径就好了。注意:因为最后有负边权存在，用dfs/bfs来求会出错。所以得用树形dp。

这道题考察了求直径的两种方法，不失为一道好题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 100010;
const ll INF = 2147483647;
ll n,k,x,y,st,ed,tem,fa[maxn],res,cnt,d[maxn],tot;
ll cur,ans;
bool vis[maxn],h[maxn];
vector<ll> e[maxn];
void dfs(ll x,ll step,ll tag){
    vis[x] = 1;
    bool pd = true;
    for(int i = 0;i < e[x].size();i++){
        if(!vis[e[x][i]]){
            pd = false;
            if(!tag)fa[e[x][i]] = x;
            dfs(e[x][i],step + 1,tag);
        }
    }
    if(pd && tem < step){
        tem = step;
        if(tag)st = x;
        else ed = x;
    }
    return;
}
void mark(ll x,ll step){
    vis[x] = 1;
    ll pd = true;
    for(int i = 0;i < e[x].size();i++){
        if(!vis[e[x][i]] && !h[e[x][i]]){
            pd = false;
            mark(e[x][i],step + 1);
        }
    }
    if(pd)cur = max(cur,step);
    return;
}
void dp(ll x){
    vis[x] = 1;
    for(int i = 0;i < e[x].size();i++){
        if(!vis[e[x][i]]){
            dp(e[x][i]);
            ans = max(ans,1ll*(d[x] + d[e[x][i]] + (h[x] == 1 && h[e[x][i]] == 1 ? -1 : 1)));
            d[x] = max(d[x],1ll*(d[e[x][i]] + (h[x] == 1 && h[e[x][i]] == 1 ? -1 : 1)));
        }
    }
}
int main()
{ 
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i = 1;i < n;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0,1);
    memset(vis,0,sizeof(vis));
    tem = 0;
    dfs(st,0,0);
    if(k == 1){
        res = (n - 1) * 2 + 1;
        tem = ed;
        while(tem != st){
            res--;
            tem = fa[tem];
        }
        cout<<res;
    }
    else{
        res = (n - 1) * 2 + 2;
        tem = ed;
        while(tem != st){
            h[tem] = 1;
            res--;
            tem = fa[tem];
        }
        h[st] = 1;
        memset(vis,0,sizeof(vis));
        dp(1);
        res -= ans;
        cout<<res;
    }
    return 0;
}