読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

(メモ) 木の中心と直径について

証明を書いていたら迷子になってしまった— ゆらふな (@yurahuna) 2016年7月18日 なのでツイートだけ貼り付けておきます。ごめんね。 参考にしたpdf: http://www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf 【中心がただ1つ or 隣接する2頂点 になることの略…

AGC001 C - Shorten Diameter

現時点で正しいと思う理解の仕方を書いたので、間違いや気になるところがあればぜひ教えてください。 問題 C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder 頂点の木がある。この木の直径を 以下にするために削除する必要のある最小の頂点数を求…

yukicoder No.399 動的な領主

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

yukicoder No.386 貪欲な領主

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

ABC014 D - 閉路

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