kazuma8128’s blog

競プロの面白い問題を解きます

2018-07-16から1日間の記事一覧

CodeChef FIBTREE Fibonacci Numbers on Tree

問題文 https://www.codechef.com/problems/FIBTREE 問題概要 サイズNの木がある. 各頂点は値を持っている(初期値0). Q個の以下のクエリをオンラインで処理せよ. クエリ1:頂点 x から頂点 y へのパス上の各頂点に順番に fib(0), fib(1), ... , fib(k) のフ…

HL分解で部分木クエリ

HL分解*1でパスクエリができることは知ってたけど同時に部分木クエリも行えることを知ったのでメモ. (もしかして割と常識なのかな?)これ https://codeforces.com/blog/entry/53170 弱い方のHL分解 元々持ってたライブラリでは, 一回 dfs で各部分木のサイズ…