StaticTopTree

更新が可能な木DP

抽象化全方位木DPやACLなどの抽象化セグ木と同じように、抽象化されており、いい感じに関数を定義してあげる感じになる。

code:cpp

enum Type { Vertex, Compress, Rake, AddEdge, AddVertex };

// g must be a rooted tree

struct StaticTopTree {

vector<vector<int>>& g;

int root; // an index of the root in g

int stt_root; // an index of the root in static top tree

vector<int> P, L, R; // parent, left child, right child

vector<Type> T; // type of vertices

int add_buf; // a variable for the member function

StaticTopTree(vector<vector<int>>& _g, int _root = 0) : g(_g), root(_root) {

int n = g.size();

P.resize(4 * n, -1), L.resize(4 * n, -1), R.resize(4 * n, -1);

T.resize(4 * n, Type::Vertex);

add_buf = n;

build();

}

private:

int dfs(int c) {

int s = 1, best = 0;

int t = dfs(d);

s += t;

}

return s;

}

int add(int k, int l, int r, Type t) {

if (k == -1) k = add_buf++;

return k;

}

pair<int, int> merge(const vector<pair<int, int>>& a, Type t) {

int u = 0;

vector<pair<int, int>> b, c;

return {add(-1, i, j, t), si + sj};

}

pair<int, int> compress(int i) {

vector<pair<int, int>> chs{add_vertex(i)};

return merge(chs, Type::Compress);

}

pair<int, int> rake(int i) {

vector<pair<int, int>> chs;

return chs.empty() ? make_pair(-1, 0) : merge(chs, Type::Rake);

}

pair<int, int> add_edge(int i) {

return {add(-1, j, -1, Type::AddEdge), sj};

}

pair<int, int> add_vertex(int i) {

return {add(i, j, -1, j == -1 ? Type::Vertex : Type::AddVertex), sj + 1};

}

void build() {

dfs(root);

stt_root = i;

}

};

using mint = atcoder::modint998244353;

vector<int> A;

struct Path {

mint a, b;

};

using Point = mint;

Path compress(Path p, Path c) { return {p.a * c.a, p.a * c.b + p.b}; };

Point rake(Point l, Point r) { return l * r; };

Point add_edge(Path d) { return d.b; };