この質問は、codechef のtravtree問題に動機付けられています。社説DFSでは、トラバーサルで各ノードの発見と終了時間を記録することにより、ツリーを配列に線形化することを推奨しています。これで、そのノードsum subtreeのセグメントで発生したイベントを合計することで、クエリにすばやく答えることができます。[discovery time, exit time](Fenwickこれらのクエリにすばやく答えるためにツリーを使用しています)。
ただし、その問題を解決するには、sum pathクエリにすばやく応答する必要もあります。つまり、 の間の最短経路に沿って発生したイベントを合計しますa, b。そんなことがあるものか？彼らが与える答えはこれです：
興味深いイベントごとに、これを更新します。
update(BT2,event_node,1);
update(BT2,out[event_node],-1);
そしてsum path(a,b)今これです：
int l = lca(a,b);
ans = query(BT2,a) + query(BT2,b) - query(BT2,l) - (l==1 ? 0 : query(BT2, parent[0][l]));
query接頭辞の合計はどこにありますか. それはどのように正しいですか?? aとの間のパスに関係のない多くのノードに遭遇する可能性があるまで、プレフィックスの合計を見るlとa!