为黑色节点数量，，那么这棵树就是符合要求的，y=1表示黑色，在每次修改结束后，输出这棵树的满意度，i次修改操作后的树上进行的。
给出一棵以 1 1 为根且包含 n n 个节点的树，每个节点都有初始颜色 col_i col i 。 col_i=1 col i =1 表示黑色， col_i=0 col i =0 表示白色。 如果这棵树的任意节点 u u 都满足：在以 u u 为根的子树中（包含 u u），黑色节点数量不少于白色节点数量，这棵树就是符合要求的。更正式得说，对于以 u u 为根的子树（包含 u u），设 B_u B u 为黑色节点数量， W_u W u 为白色节点数量。如果 {forall}uin[1,n] ∀u∈[1,n]，都有 W_uleq B_u W u ≤B u ，那么这棵树就是符合要求的。 现在有一种补全操作：选择任意一个节点 u u，然后给 u u 添加一个儿子节点 new new，节点 new new 染黑或染白。 如果至少需要执行 res res 次补全操作，才能使这棵树符合要求，那么称这棵树的满意度为 res res。 现在有 q q 次修改，每次修改用二元组 (x,y) (x,y) 表示，意思是将节点 x x 修改成颜色 y y，如果 y=0 y=0 表示白色， y=1 y=1 表示黑色。在每次修改结束后，输出这棵树的满意度。 需要注意的是，修改操作不是独立的，也就是说，第 i+1 i+1 次修改操作是在第 i i 次修改操作后的树上进行的。
标签： HBC259249小宝与木棍 贪心 过关题目树题解
