問題概要 ノード数V( 解法 クエリを受ける前に全ての答えを計算しておく。まず、前処理として始点から各頂点への距離と終点から各頂点への距離をdijkstraで求めておく。 また、ついでに始点からのshortest path treeとshortest pathを計算しておく。このとき…

問題概要 ノード数N( 解法 適当な頂点を選んで根付き木にして、LCAを計算しておく。Sの元(v,u)は、lca(u,v)!=u or vのとき(v,lca(v,u)), (u,lca(v,u))と変換してもよいことが分かる。この様な変換を加えておくと、再帰的に計算するとき上手く値をキャンセル…