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;
} 
全部评论
(1) 回帖