《黑白树》结题报告

题目分析

有一个树，有 个结点，然后每个结点 ，上有个权值 ，开始的时候点都是白色的.

你可以选结点，这个结点可以使在它和根结点的链子上 到 的点都染成黑色 ，问你如何选择最少的点，可以让这个树都变黑。（没错这是我看错的题目，但是没有影响，而且还简单了。

思路与想法

这不就随便搞嘛。一看不是贪心就是dp。尝试着描述了一下状态，发现不好描述也不好转移，那么就搞一下贪心。

不妨在 Dfs 的过程中计算答案。有个很明显的 做法。

1. 找到未被覆盖的节点组成的树的一个叶子节点
2. 在它和它已经被覆盖的子树中找到一个点，使得其向上能覆盖到的 及 的祖先们尽可能多
3. 如此反复，知道没有 可以取

这个过程可以用 dfs 来描述，做一个前缀的最多覆盖的长度即可，这样子可以使得我们的复杂度优化为

#include <bits/stdc++.h>
const int N = 1e5 + 1;
int n, fa[ N ], ans, k[ N ];
std::vector < int > v[ N ];
int Dfs( int u )
{
 int mx = 0;
 // 前缀（叶子到根）最大值
 for( auto &i: v[ u ] )
  mx = std::max( mx, Dfs( i ) );
 if( !mx )
  return ++ans, k[ u ] - 1;
 // 更新它爸爸的值
 k[ fa[ u ] ] = std::max( k[ fa[ u ] ], k[ u ] - 1 );
 return mx - 1;
}
int main( )
{
 std::ios::sync_with_stdio( false );
 std::cin >> n;
 for( int i = 1; i < n; ++i )
 {
  std::cin >> fa[ i + 1 ];
  v[ fa[ i + 1 ] ].push_back( i + 1 );
 }
 for( int i = 1; i <= n; ++i )
  std::cin >> k[ i ]; 
 Dfs( 1 );
 std::cout << ans;
 return 0;
}