题意:给定一棵n个点边权为1的树,允许再建立\(K(K=1,2)\)条边,求从节点1出发,遍历所有的点后,回到节点1的最小距离.
分析:嗯.蓝书上讲得挺详尽的.\(K=1\)时,答案就是\(2*(n-1)-l1\),\(l1\)表示树的直径长度.\(K=2\)时,答案就是\(2*(n-1)-l1-l2\),\(l2\)表示将\(l1\)上的所有边权取反后的新直径.
很诡异的是,第一次求直径的时候因为要记录直径上的路径(为了把边权取反)所以要用两次\(DFS/BFS\)求直径法.第二次求直径的时候因为树上有负权,所以只能用\(dp\)法.两次都限制了求直径的方法.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=2e5+5;
int a[N],b[N];
int n,k,l1,l2,dis[N],pre[N];
int tot,head[N],nxt[N],to[N],w[N];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
inline void dfs1(int u,int fa){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];if(v==fa)continue;
dis[v]=dis[u]+w[i];dfs1(v,u);
}
}
inline void dfs2(int u,int fa){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];if(v==fa)continue;
dis[v]=dis[u]+w[i];pre[v]=u;dfs2(v,u);
}
}
map<int,int>Map;
inline void dp(int u,int fa){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];if(v==fa)continue;
dp(v,u);
l2=max(l2,dis[u]+dis[v]+w[i]);
dis[u]=max(dis[u],dis[v]+w[i]);
}
}
int main(){
n=read();k=read();
for(int i=1;i<n;++i){
a[i]=read();b[i]=read();
add(a[i],b[i],1);add(b[i],a[i],1);
}
dfs1(1,0);
int maxn=0,pos1,pos2;
for(int i=1;i<=n;++i)if(dis[i]>maxn)maxn=dis[i],pos1=i;
memset(dis,0,sizeof(dis));dfs2(pos1,0);
maxn=0;for(int i=1;i<=n;++i)if(dis[i]>maxn)maxn=dis[i],pos2=i;
tot=0;memset(head,0,sizeof(head));
while(pos2!=pos1){
add(pre[pos2],pos2,-1);add(pos2,pre[pos2],-1);
Map[pos2]=pre[pos2];pos2=pre[pos2];++l1;
}
if(k==1){
printf("%d\n",2*(n-1)-(l1-1));
return 0;
}
for(int i=1;i<n;++i){
if(Map[a[i]]!=b[i]&&Map[b[i]]!=a[i]){
add(a[i],b[i],1);add(b[i],a[i],1);
}
}
memset(dis,0,sizeof(dis));
dp(1,0);
printf("%d\n",2*n-l1-l2);
return 0;
}
[APIO2010]巡逻