2023.8.3 训练
A
有一个 01 矩阵，求最少取反若干矩阵，使得存在一条由左上到右下仅为 0 的路径，
且只能向下向右走。
设 \(f(i,j,0/1)\) 表示走到 \((i.j)\)，且那个点为 0/1 的最小值。
用 \(f(i-1,j),f(i,j-1)\) 更新 \(f(i,j)\) 即可。
B [AGC010C] Cleaning
有一棵树，每次可以选择连接两个叶子的路径使得上面的点 -1。
每个点由初始值，问能否让所有点归零。
先选择一个非叶子的点做根。
考虑计算 \(f_u\) 为一个点向上“伸出”的路径条数，显然叶子节点伸出 \(a_u\)。
考虑一个节点 \(u\)，它的儿子的 \(f\) 总和记为 \(s\).
若 \(s<a_u\)，则无解，因为没有那么多路径可以减少 \(a_u\) 至 0,。
对于 \(s-a_u\) 的部分，这些只能在 \(u\) 处弯折。
考虑 \(u\) 最多弯折多少边，记儿子最大的 \(f\) 为 \(mx\)，答案是 \(\min(s/2,s-mx)\).
若 \(s-a_u>\min(s/2,s-mx)\)，那么无解。
若有解，\(f_u=a_u-(s-a_u)\).