題目鏈接：LUK-Triumphal arch

---

首先考慮二分最小的k。

然后轉(zhuǎn)為判定合法性。我們可以樹形dp。

dp[x] 為當(dāng)前 B 在x點(diǎn)，然后A需要在子樹中染色的最小點(diǎn)數(shù)。

dp[x] = Σ dp[v]+1 - k

最后判斷dp[1]==0即可。

---

AC代碼：

#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=3e5+10; int n,dp[N]; vector<int> g[N]; void dfs(int x,int fa,int mid){dp[x]=0;for(int to:g[x]) if(to!=fa) dfs(to,x,mid),dp[x]+=dp[to]+1;dp[x]=max(0,dp[x]-mid); } inline int check(int mid){dfs(1,0,mid); return !dp[1];} signed main(){cin>>n;for(int i=1,a,b;i<n;i++) scanf("%d %d",&a,&b),g[a].push_back(b),g[b].push_back(a);int l=0,r=n;while(l<r){int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}cout<<l;return 0; }

總結(jié)

以上是生活随笔為你收集整理的LUK-Triumphal arch的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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