鏈接：https://ac.nowcoder.com/acm/problem/13249
來源：牛客網

題目描述
一棵n個點的有根樹，1號點為根，相鄰的兩個節點之間的距離為1。樹上每個節點i對應一個值k[i]。每個點都有一個顏色，初始的時候所有點都是白色的。
你需要通過一系列操作使得最終每個點變成黑色。每次操作需要選擇一個節點i，i必須是白色的，然后i到根的鏈上（包括節點i與根）所有與節點i距離小于k[i]的點都會變黑，已經是黑的點保持為黑。問最少使用幾次操作能把整棵樹變黑。
輸入描述:
第一行一個整數n (1 ≤ n ≤ 10^5)
接下來n-1行，每行一個整數，依次為2號點到n號點父親的編號。
最后一行n個整數為k[i] (1 ≤ k[i] ≤ 10^5)

樣例解釋:
對節點3操作，導致節點2與節點3變黑
對節點4操作，導致節點4變黑
對節點1操作，導致節點1變黑
輸出描述:
一個數表示最少操作次數
示例1
輸入
復制
4
1
2
1
1 2 2 1
輸出
復制
3
我們從每個葉子節點往上回溯。
如果子樹里面的點染不到這個點就ans++,然后將這個點的染色值傳上去。
如果可以染到這個點，就更新父節點的染色值，然后記錄當前節點染色到的最大值，并且返回。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{int to;int next; }e[maxx<<1]; int tot,head[maxx<<1],k[maxx],fa[maxx],n; /*----------事前準備---------*/ inline void init() {memset(head,-1,sizeof(head));tot=0; } inline void add(int u,int v) {e[tot].to=v,e[tot].next=head[u],head[u]=tot++; } /*---------樹形dp----------*/ inline int dfs(int u,int f,int &ans) {fa[u]=f;int now=0;for(int i=head[u];i!=-1;i=e[i].next){int to=e[i].to;if(to==f) continue;now=max(now,dfs(to,u,ans));}if(now<=1)//子樹里面的點染不到當前的節點{ans++;return k[u];}k[f]=max(k[f],k[u]-1);//如果能夠染到的話，就更新父親節點的染色值，取最大值return now-1; }int main() {int x;while(~scanf("%d",&n)){init();for(int i=2;i<=n;i++){scanf("%d",&x);add(i,x);add(x,i);}for(int i=1;i<=n;i++) scanf("%d",&k[i]);int ans=0;dfs(1,0,ans);cout<<ans<<endl;}return 0; }

努力加油a啊，(^o)/~

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的黑白树（牛客网+树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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