とても面白いと思ったけど、帰着によってはそうでもないらしい？ 問題 Never Wait for Weights | Aizu Online Judge N個のアイテムがある。M個のクエリが与えられる。クエリは次の2種類である。 ! a b w アイテムa, bの重さの差はwである(w_b - w_a = w) ? a…

"木上のimos法"というテク。 問題 No.399 動的な領主 - yukicoder N頂点の無向木がある。Q人の人が u_i から v_i へ最短経路で移動する。人が頂点を通過するとき、(自分より前にその頂点を通った人の人数) + 1 のコストがかかる。Q人の移動コストの総和を求…

クラスにしたのでとりあえず。 日本語コメント保存用 Verify: Lowest Common Ancestor | Aizu Online Judge #include <bits/stdc++.h> using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,</bits/stdc++.h>…

問題 N頂点の無向木で表される国がある。各頂点を通るには1人当たり税金Uiがかかる。 今からQ個のクエリが与えられる。i番目のクエリは頂点Aiから頂点BiにCi人が移動することを表す。 この国で支払われる税金の合計額を求めよ。 制約 2 <= N <= 100000 0 < U…

どこからLCAなんて発想が出てくるの！？と思った人用。 問題 木に辺を追加したときの閉路長を各クエリに対して求めよ。 制約 頂点数: クエリ数: 解法 辺 を追加したときの閉路長は、もとのグラフにおける点 と点 との最短距離を とすると、 (追加する辺の長…