題面

?二分答案，問題就轉化為了一個可行性問題，因為我們不知道國王會往哪里走，所以我們要在所有他可能走到的點建造，考慮用樹形DP解決(這個DP還是比較好寫的，你看我這個不會DP的人都能寫出來=。=)

定義$dp[x]$表示以$x$這個點為根的子樹中(不包含x)需要修建的次數(因為1號點已經修好了，最后回來不用管)，那么對于每個二分出的$mid$有$dp[x]=max((\sum dp[son[i]])+sons[x]-mid)$，其中$sons[i]$表示它(直接的)兒子的個數，顯然對于每個點是必須先把所有兒子建好的。最后如果$dp[1]=0$說明可行

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=300005; 6 int n,t1,t2,cnt,l,r,mid,ans; 7 int p[N],noww[2*N],goal[2*N]; 8 int son[N],dp[N]; 9 void link(int f,int t) 10 { 11 noww[++cnt]=p[f]; 12 goal[cnt]=t,p[f]=cnt; 13 } 14 void MARK(int nde,int fth) 15 { 16 for(int i=p[nde];i;i=noww[i]) 17 if(goal[i]!=fth) MARK(goal[i],nde),son[nde]++; 18 } 19 void DFS(int nde,int fth) 20 { 21 int tmp=0; 22 for(int i=p[nde];i;i=noww[i]) 23 if(goal[i]!=fth) DFS(goal[i],nde),tmp+=dp[goal[i]]; 24 dp[nde]=max(tmp+son[nde]-mid,0); 25 } 26 bool check(int x) 27 { 28 memset(dp,0xcf,sizeof dp); 29 DFS(1,0); return !dp[1]; 30 } 31 int main () 32 { 33 scanf("%d",&n),r=n; 34 for(int i=1;i<n;i++) 35 { 36 scanf("%d%d",&t1,&t2); 37 link(t1,t2),link(t2,t1); 38 } 39 MARK(1,0); 40 while(l<=r) 41 { 42 mid=(l+r)/2; 43 if(check(mid)) r=mid-1,ans=mid; 44 else l=mid+1; 45 } 46 printf("%d",ans); 47 return 0; 48 } View Code

?

轉載于:https://www.cnblogs.com/ydnhaha/p/9682674.html

總結

以上是生活随笔為你收集整理的解题：POI 2013 Triumphal arch的全部內容，希望文章能夠幫你解決所遇到的問題。

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