【木のDAG】 木に単一の方向性を持たせるとDAGになる 割り振り直した頂点IDは降順あるいは昇順になる このようなDAGは木でもあるので元の頂点IDはユニークでもある 頂点の割り振り直し方法 ・DAGの最長経路＝木の根からの深さ＝末端からMAXのBFS、で頂点IDを…

フィボナッチ数列の計算（メモ化再帰のテンプレートとしても使える） #include <bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; auto mf = [&](auto self, ll now, vl& memo, ll inf) -> void { if (now == 1 || now == 2) { // 末端は定数</ll></bits/stdc++.h>…

ウェーブレット行列 任意区間のK番目の要素を高速に取得するデータ構造 https://ei1333.github.io/library/structure/wavelet/wavelet-matrix.cpp.html前計算 クエリ WaveletMatrix(v): 各要素の高さ v を初期値として構築する. access(k): k 番目の要素を返…