全方位木DP ライブラリ

参考リンク

内容

ある頂点を根とした木に関するDPを，うまいこと再計算せずにこねこねして

https://gyazo.com/d5935124fedf8ba3ea6b5da717c70da7

https://gyazo.com/fc70f62369c981ea2f2b3652664ab784

https://gyazo.com/95ae5667df0576794349d8d3673b2857

https://gyazo.com/8adfd53b4c8262c1542e6d43e23ead37

まず，通りがけ順を記録し

後ろ側から，ボトムアップに根０から下方向を計算する．

あとは，根０に近いほうから，反対側は計算できているため，その方向に計算する．

計算をするときはDPというユーザ定義クラスを準備して

func(merge 処理　小部分木に対して行う)

addnode(仕上げ　自分自身vの答えにするためのもの)

を書く

コード

code:cpp

template<class T>

class ReRooting {

private:

int N;

// 頂点iのj番目に隣接している頂点

vector<vector<int>> G;

vector<vector<int>> idxs;

// 頂点iからの答え

vector<T> result;

// 頂点iを親としたとき

vector<vector<T>> dp;

T identity;

// func(x, y)

// 値x,yを処理するモノイド

function<T(T, T)> func;

// add_node(x, u)

// 頂点uを根付き木としたときその子供のモノイドを計算した後の最後の一手

// u自体を加えるイメージ

function<T(T, int)> add_node;

public:

ReRooting(int N, vector<pair<int, int>> &edges, T identity, function<T(T, T)> func, function<T(T, int)> add_node) : N(N), identity(identity), func(func), add_node(add_node) {

G = vector<vector<int>>(N);

idxs = vector<vector<int>>(N);

for (auto &&e: edges) {

int f = e.first;

int t = e.second;

}

dp = vector<vector<T>>(N);

result = vector<T>(N);

if (N > 1) reroot();

}

T query(int v) {

}

private:

void reroot() {

vector<int> parent(N);

vector<int> order;

//region init_ordered_tree

stack<int> stk;

stk.push(0);

while (!stk.empty()) {

auto v = stk.top();

stk.pop();

order.push_back(v);

stk.push(to);

}

}

//endregion

//region from_leaf (bottom-up)

for (int i = N - 1; i >= 1; i--) {

// 親pとする部分木vの答え

T aum = identity;

// vの親pがvに何番目で隣接しているか

int p_idx = -1;

p_idx = j;

continue;

}

}

}

//endregion

//region to_leaf(top-down)

for (int i = 0; i < N; i++) {

T aum = identity;

// 頂点vの最後から 先頭から数えてi番目に隣接している頂点までの値

tails.back() = identity;

for (int j = 0; j < tails.size(); j++) {

}

}

//endregion

}

};