《黑白树》结题报告

题目分析

有一个树，有 $n$ 个结点，然后每个结点 $x$ ，上有个权值 $k[x]$ ，开始的时候点都是白色的.

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

思路与想法

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

不妨在 Dfs 的过程中计算答案。有个很明显的 $O(n^2)$ 做法。

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

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

#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;
}