差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 最新のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/04] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/05] – ikatakos | ||
|---|---|---|---|
| 行 231: | 行 231: | ||
| * 頂点 $v$ を根とする部分木で、 | * 頂点 $v$ を根とする部分木で、 | ||
| * 今まで切った辺が $i$ 本の時の、 | * 今まで切った辺が $i$ 本の時の、 | ||
| - | * $v$ を含む連結成分の__頂点の値が全て正であるような切り方__の中で、 | + | * $v$ を含む連結成分の__頂点の値が全て正であるような切り方__の中で |
| * $v$ を含む連結成分の和の最小値 | * $v$ を含む連結成分の和の最小値 | ||
| * (B) $DP2[v][i]=$ | * (B) $DP2[v][i]=$ | ||
| 行 241: | 行 241: | ||
| ただし、$v$ を含む連結成分" | ただし、$v$ を含む連結成分" | ||
| - | 条件の1つでは、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが常によい。 | + | $i$ の範囲の上限は、部分木のサイズとなる。 |
| - | 「連結成分内の頂点が全て正」の場合は和は関係ないので $DP1$ は必ずしも最小値でなくてもよいような気も一瞬するが、これは暫定であるため、将来的に負の頂点と統合されて「連結成分内の和が負」の方の条件で切られることになるかも知れない。 | + | |
| - | よって両方とも、和を低く保つようにDPを行うのがよい。 | + | (B)では、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが常によい。 |
| + | |||
| + | 本来は(A)の場合は和は関係ないので、$i$ 本の時にできるかできないかのみ保持しておくだけでよかったらしい。 | ||
| < | < | ||
| 行 266: | 行 268: | ||
| ===DP=== | ===DP=== | ||
| - | DPの更新を楽にするため、「不可」を示す数を極端に大きな数とする。（頂点の和になり得ない数。全頂点が最大値の$10^9$であり、$N=5000$ なので、$5 \times 10^{12}$ より大きい数） | + | DPの更新を楽にするため、「不可」を示す数を極端に大きな数(inf)とする。（頂点の和になり得ない数。全頂点が最大値の$10^9$であり、$N=5000$ なので、$5 \times 10^{12}$ より大きい数） |
| すると、上の例の '' | すると、上の例の '' | ||
