問題タブ [lazy-propagation]

最近、 Gravity Treeという問題に出くわしました 。自分では解決できなかったので、社説を確認しました. 著者の解決策は、頂点を 1 回 dfs し、各ノードに頂点から中心までの距離が含まれるセグメント ツリーを形成することでした。次に、彼は 2 番目の dfs について言及します (それが何をしているのかわかりません。彼のデータ構造を印刷しようとしましたが、彼が実際に何をしようとしているのかを知らずに、まったく意味がありません)。彼が書いた言葉は少し難しすぎて理解できなかった. セグメント ツリー、dfs、遅延伝播とは何かを知っています。しかし、このソリューションに頭を悩ませることはできません。そして、解決策がわからないので、とても不安で、他のことに集中できません。誰かがより明確な説明をしてくれるとうれしいです。混乱している他の人でさえも恩恵を受けるように。前もって感謝します ：）

問題設定者は頑固です。