正題

---

題目大意

剛開始一棵樹，在樹中加入k條邊(k<=2)使得這些邊都得走過的情況下，每個點都到達并回到原點的最少邊。

---

解題思路

首先我們發現如果不加邊的話答案是$2?(n?1)$。
之后我們考慮$k=1$的情況，我們找樹的直徑，然后在兩個端點之間加邊，這樣就可以少跑直徑長度-1這么多。設直徑長度為$dis$，答案是$2?(n?1)?dis+1$。

之后我們考慮$k=2$的情況。我們發現如果之后再找一條直徑和之前的直徑沒有重邊的話答案就是$2?(n?1)?dis?dis2+2$。

有重邊怎么辦，我們發現如果有重邊，那么重邊就會多跑一次。所以我們可以把第一次直徑上所有邊權都變成$?1$，我們就可以直接$2?(n?1)?dis?dis2+2$。

根據$zyc$的說法，第一次用$dfs$方便記錄路徑，第二次有負邊權所以得用$dp$。

完美解決該題

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> #define N 100010 using namespace std; int n,k,dis,dis2,ls[N],tot; int pre[N],last,f[N],p,x,y; struct node{int to,w,next; }a[2*N]; void addl(int x,int y,int w)//加邊 {a[++tot].to=y;a[tot].w=w;a[tot].next=ls[x];ls[x]=tot; } void dfs(int x,int fa,int disr)//第一次求直徑 {if(disr>dis) dis=disr,p=x;for(int i=ls[x];i;i=a[i].next)if(a[i].to!=fa)pre[a[i].to]=x,dfs(a[i].to,x,disr+a[i].w); } void change(int x,int end)//改變邊權 {if(x==end) return;for(int i=ls[x];i;i=a[i].next)if(a[i].to==pre[x]){a[i].w=-1;a[i^1].w=-1;change(a[i].to,end);} } void dp(int x,int fa)//第二次求直徑 {for(int i=ls[x];i;i=a[i].next)if(a[i].to!=fa){int y=a[i].to;dp(a[i].to,x);dis2=max(dis2,f[x]+f[y]+a[i].w);f[x]=max(f[y]+a[i].w,f[x]);} } int main() {tot=1;scanf("%d%d",&n,&k);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);addl(x,y,1);addl(y,x,1);}dfs(1,0,0);last=p;dis=0;dfs(p,0,0);if(k==1){printf("%d",2*(n-1)-dis+1);return 0;}change(p,last);dp(1,0);printf("%d",2*(n-1)-dis-dis2+2); }

總結

以上是生活随笔為你收集整理的P3629-[APIO2010]巡逻【树的直径】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。