?id=1912 (题目链接)
题意给出一棵树，要求在树上添加K(1 or 2)条边，添加的边必须经过一次，使得从1号节点到达每个节点最后返回1号节点所经过的路径最短。
Solution如果不添加边，那么答案一定是每条边经过两次。
如果K为1，那么答案就很明显对吧，找到树的直径，链接直径两端点，使得直径上的边只经过一次，答案最优。
那么如果K为2，我们会发现，当两个环有变重叠时，重叠的边同样是要经过2次。也就是说第一次添加边时构成的环上面的边，如果在第二次添加是仍在环上，那么并不会对答案有贡献。所以我们第二次添加边时，先将树的直径上的边的边权改为-1，之后跑一遍树上最长链(注意有负权，，所以不能找树的直径)即可。
代码// bzoj1912 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define LL long long #define inf 2147483640 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std; const int maxn=100010; struct edge {int to,next,w;}e[maxn<<1]; int head[maxn],deep[maxn],rt[2],f[maxn][2],son[maxn]; int n,k,cnt,p; void link(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=1; e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].w=1; } void dfs(int x,int fa) { if (deep[rt[p]]<deep[x]) rt[p]=x; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) { deep[e[i].to]=deep[x]+e[i].w; dfs(e[i].to,x); } } int work(int x,int fa) { if (x==rt[1]) return 1; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) if (work(e[i].to,x)) { e[i].w=e[i&1?i+1:i-1].w=-1; return 1; } return 0; } void dd(int x,int fa) { for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) { dd(e[i].to,x); if (f[x][1]<f[e[i].to][1]+e[i].w) f[x][1]=f[e[i].to][1]+e[i].w,son[x]=e[i].to; else f[x][0]=max(f[x][0],f[e[i].to][1]+e[i].w); } if (f[x][0]==-inf) f[x][0]=0;if (f[x][1]==-inf ) f[x][1]=0; } void dp(int x,int fa,int d) { if (f[x][1]<d) f[x][0]=f[x][1],f[x][1]=d,son[x]=0; else f[x][0]=max(f[x][0],d); for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) { if (son[x]==e[i].to) dp(e[i].to,x,e[i].w+f[x][0]); else dp(e[i].to,x,e[i].w+f[x][1]); } } int main() { scanf("%d%d",&n,&k); for (int u,v,i=1;i<n;i++) { scanf("%d%d",&u,&v); link(u,v); } dfs(1,0);deep[rt[p++]]=0;dfs(rt[0],0); int ans=(n-1)*2-deep[rt[1]]; if (k==1) {printf("%d",ans+k);return 0;} work(rt[0],0); for (int i=1;i<=n;i++) f[i][0]=f[i][1]=-inf; deep[1]=0;dd(1,0); dp(1,0,-inf); int tmp=0; for (int i=1;i<=n;i++) tmp=max(tmp,f[i][1]); printf("%d",ans-tmp+k); return 0; }
【bzoj1912】 Apio2010—patrol 巡逻