全方位木DP
概要
それぞれの頂点を根としたDPを全頂点で $ O(N)で行う。
抽象化ができる。以下に抽象化全方位木DPを貼る。出典 DataはDPテーブルが持つ値の型。llや、pair<ll,ll>など。
Costは辺に値があるときにその型。なければ適当にllにしておき、全て1にしておけばよい。
mergeはDPテーブルのマージ。子から上がってきた情報を、親が今持っている情報とどうマージするか。
eはDPテーブルをマージするときの単位元。つまり、mergeしてもmergeされる側の値が変わらないような値。
leafは子が存在しない頂点（葉）が返す値。親に遷移するときにapplyは呼ばれることに注意。
applyは子から親へ遷移するときの変化。例えば部分木サイズなら1増えるなど。
code:cpp
template <typename Cost>
struct Edge {
int src, to;
Cost cost;
Edge(int s, int t, Cost c = 1) : src(s), to(t), cost(c) {}
operator int() const { return to; }
};
template <typename Cost>
struct Graph : vector<vector<Edge<Cost>>> {
Graph(int n) : vector<vector<Edge<Cost>>>(n) {}
void add_edge(int s, int t, Cost c = 1) { (*this)s.emplace_back(s, t, c); } };
template <typename Cost, typename Data, Data (*merge)(Data, Data), Data (*e)(),
Data (*leaf)(), Data (*apply)(Data, int, int, Cost)>
struct Rerooting : Graph<Cost> {
vector<Data> dp, memo;
Rerooting(int n) : Graph<Cost>::Graph(n) {}
vector<Data> run() {
memo.resize((*this).size(), e());
dp.resize((*this).size());
dfs1(0, -1);
dfs2(0, -1, e());
return dp;
}
void dfs1(int c, int p) {
bool upd = false;
for (Edge<Cost> &d : (*this)c) { if (d == p) continue;
dfs1(d, c);
upd = true;
memoc = merge(memoc, apply(memod, d, c, d.cost)); }
if (!upd) memoc = leaf(); }
void dfs2(int c, int p, const Data &val) {
vector<Data> ds{val};
for (Edge<Cost> &d : (*this)c) { if (d == p) continue;
ds.push_back(apply(memod, d, c, d.cost)); }
int n = ds.size(), idx = 1;
vector<Data> head(n + 1, e()), tail(n + 1, e());
for (int i = 0; i++ < n;) headi = merge(headi - 1, dsi - 1); for (int i = n; i-- > 0;) taili = merge(taili + 1, dsi); for (Edge<Cost> &d : (*this)c) { if (d == p) continue;
dfs2(d, c, apply(sub, c, d, d.cost));
idx++;
}
}
};
ll n,m;
using Data = long long;
using Cost = long long;
Data merge(Data a, Data b) { return a*b%m; }
Data e() { return 1; }
Data leaf() { return 1; }
Data apply(Data a, int c, int, Cost w) { return a+1; }
using Reroot = Rerooting<Cost,Data,merge,e,leaf,apply>;
bool solve(){
cin >> n >> m;
Rerooting<Cost,Data,merge,e,leaf,apply>g(n);
rep(i,n-1){
LL(a,b);
a--,b--;
g.add_edge(a,b,1);
g.add_edge(b,a,1);
}
auto ans = g.run();
rep(i,n){
}
return false;
}