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) 回帖