題目描述

給出一個 $n$ 個節點的樹，$1$ 號點為根。現要將其中一些點染成黑色，使得每個葉子節點（不包括根節點）到根節點路徑上的黑點數相同。求最多能夠染多少個黑點。

---

題解

貪心

顯然有結論：選擇的黑點盡量靠近葉子節點。

并且顯然每個點到根節點路徑上的黑點數是：深度最小的葉子節點到根節點路徑上的點數。

那么首先預處理出每個點子樹內深度最小的葉子節點的深度，然后進行貪心過程：顯然如果一個點染黑，那么它到其子樹內深度最小的葉子節點路徑上的所有點都要染黑。我們維護每個點到根節點的路徑上染了多少黑點，就能根據已經染黑的節點數和它到其字數內深度最小的葉子節點路徑上的點數即可判斷出當前點是否能夠選擇。

時間復雜度 $O(n)$

#include <cstdio> #include <algorithm> #define N 100010 using namespace std; int head[N] , to[N << 1] , next[N << 1] , cnt , deep[N] , md[N] , now[N] , ans; inline void add(int x , int y) {to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt; } void dfs(int x , int fa) {int i;if(x != 1 && !next[head[x]]) md[x] = deep[x];else md[x] = 1 << 30;for(i = head[x] ; i ; i = next[i])if(to[i] != fa)deep[to[i]] = deep[x] + 1 , dfs(to[i] , x) , md[x] = min(md[x] , md[to[i]]); } void solve(int x , int fa) {int i;now[x] = now[fa];if(now[fa] + md[x] - deep[x] == md[1]) now[x] ++ , ans ++ ;for(i = head[x] ; i ; i = next[i])if(to[i] != fa)solve(to[i] , x); } int main() {int n , i , x , y;scanf("%d" , &n);for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);dfs(1 , 0);solve(1 , 0);printf("%d\n" , ans);return 0; }

?

轉載于:https://www.cnblogs.com/GXZlegend/p/8244237.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【uoj#139】[UER #4]被删除的黑白树 贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

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