題目大意：給一顆樹，1號(hào)節(jié)點(diǎn)已經(jīng)被染黑，其余是白的，兩個(gè)人輪流操作，一開始B在1號(hào)節(jié)點(diǎn)，A選擇k個(gè)點(diǎn)染黑，然后B走一步，如果B能走到A沒染的節(jié)點(diǎn)則B勝，否則當(dāng)A染完全部的點(diǎn)時(shí)，A勝。求能讓A獲勝的最小的k

?

首先易知B不會(huì)走回頭路，走回頭路代表自己毫無(wú)貢獻(xiàn)還讓A多染了兩次色

所以B的路徑就是從根到葉子節(jié)點(diǎn)

先二分一下答案轉(zhuǎn)成判定性問題

然后TreeDP，f[i]表示當(dāng)B現(xiàn)在在i時(shí)，需要提前染好i的子樹（不包含i）中的多少個(gè)節(jié)點(diǎn)才能保證A獲勝

例如一個(gè)節(jié)點(diǎn)下方有X個(gè)葉子節(jié)點(diǎn)，而A每次只能染K個(gè)，那就需要提前染好其中的X-K個(gè)才能保證A獲勝

那么顯然可以得到f[i]=max(∑(f[j]+1)-K,0)? (j是i的兒子)

最后看f[1]是否=0就好了

注意這題有坑，n=1輸出0

?

#include<iostream> #include<cstdio> #define N 300010 using namespace std; int to[N<<1],nxt[N<<1],pre[N],cnt; int fa[N]; void ae(int ff,int tt) {cnt++;to[cnt]=tt;nxt[cnt]=pre[ff];pre[ff]=cnt; } int f[N]; int D; void build(int x) {int i,j;int tot=0;for(i=pre[x];i;i=nxt[i]){j=to[i];if(j==fa[x]) continue;fa[j]=x;build(j);tot+=f[j]+1;}f[x]=max(tot-D,0); } int main() {int n;scanf("%d",&n);if(n==1) {puts("0");return 0;}int i,j,x,y;for(i=1;i<n;i++){scanf("%d%d",&x,&y);ae(x,y);ae(y,x);}int l=1,r=n-1;while(l<r){for(i=1;i<=n;i++) f[i]=0;D=(l+r)>>1;build(1);if(f[1]==0) r=D;else l=D+1;}printf("%d",l); }

?

總結(jié)

以上是生活随笔為你收集整理的BZOJ3420: Poi2013 Triumphal arch的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。