Tree

LCA Doubling + Sparse Table(?)

http://omochan.hatenablog.com/entry/2017/07/15/181512この問題で師匠のコードを見ていたら、Sparse Tableっぽいの使っているなあと思ったので僕も実装してみました。 vcost[v][k]:vから2^k個先の親までのpathで一番小さい辺のcostとすると、ダブリングと…

CF AIM Tech Round4C: Upgrading Tree

http://codeforces.com/contest/843/problem/C重心を根としてウニみたいなグラフを構成します。具体的な方法は http://kmjp.hatenablog.jp/entry/2017/09/05/0900 ここに書いてあります。 重心が複数個あるときもほとんど同じです。(複数といっても高々2つな…

CF434E: Arkady and a Nobody-men

http://codeforces.com/contest/860/problem/EHL分解やるだけで通ってしまった… depthの浅い頂点から順番に見ていき、根まで+1をする更新を行うことで求められます。segtreeでやったら遅かったのでbitにして1824ms/2000msでAC。 struct BIT { //0-origin!!! …

Euler Tour

Euler Tourは木を直線にして扱いやすくするテクニックです。 これを使うとLCA、二点間のpathの長さがO(logN)で求められます。でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。 HL分解は実装が重い…

AtCoder Grand Contest 014E: Blue and Red Tree

http://agc014.contest.atcoder.jp/tasks/agc014_eマージテクの問題を一つ解きたくなったので。詳しくは解説に任せるが、青と赤の辺が重なっている部分を一つの頂点に併合していく感じの操作が出来れば良い。 これは各頂点から生えてる辺を持ってマージテク…

UVa 12161: Ironman Race in Treeland

UVaデビューです。UVa Online Judge重心分解。問題はどうやってsubtree間のpathを高速に処理するか。 まず各subtreeの重心からのpathについてdamageとlengthの合計を求めておく。 それをすべて一つの配列に入れてsortして、その配列と同じ大きさのsegtreeに…

POJ 2114: Boatherds

http://poj.org/problem?id=2114蟻本と同じことやるだけ…と思うがO(MNlog^2N)になって通るわけないだろ!と思い、ググってみるとどうやらそれでいけるらしいと分かったので、submitしてみるとTLE。途方に暮れているとvectorにstaticつけると速くなるよって書…

POJ 1741: Tree

http://poj.org/problem?id=1741重心分解。解法は蟻本にある。適当に整備して使いやすいようにした。updateだけいじればよくなっている。updateも重心を根とする木について考えれば良いので楽。 namespace CD { //centroid decomposition struct edge { int …

AtCoder Regular Contest 078D: Fennec VS. Snuke

http://arc078.contest.atcoder.jp/tasks/arc078_b解法自体は簡単だけど、バグらせたので。 こういう境界でバグらせやすい問題は[a b)の区間で考えるのがよさそう。 [a (a+b)/2)にすると半分、またはそれより1小さくなり、 [a (a+b+1)/2)にすると半分、また…

Codeforces Round #419C: Karen and Supermarket

http://codeforces.com/contest/815/problem/C3乗っぽいけど2乗な木dp。 5000*5000*2のlong longの配列持ったらMLEした。 さらに初期化を適当にやりすぎてO(N^3)になってしまった。 直してAC。 int N, B; vector<int> G[MAX_N]; int dp[MAX_N][MAX_N][2]; int dp2</int>…

Codeforces Round #423B: High Load

http://codeforces.com/contest/827/problem/B最初にrootを一つ決めて、あとはkコずつrootからまんべんなくつけていけば、木の高さが最小、かつその時の一番rootから離れているedgeの個数も最小になるのでこれが求めるグラフとなる。 int N, K; void solve()…