From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- content/graph/reroot.cpp | 62 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) create mode 100644 content/graph/reroot.cpp (limited to 'content/graph/reroot.cpp') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp new file mode 100644 index 0000000..4c6a748 --- /dev/null +++ b/content/graph/reroot.cpp @@ -0,0 +1,62 @@ +// Usual Tree DP can be broken down in 4 steps: +// - Initialize dp[v] = identity +// - Iterate over all children w and take a value for w +// by looking at dp[w] and possibly the edge label of v -> w +// - combine the values of those children +// usually this operation should be commutative and associative +// - finalize the dp[v] after iterating over all children +struct Reroot { + using T = ll; + + // identity element + T E() {} + // x: dp value of child + // e: index of edge going to child + T takeChild(T x, int e) {} + T comb(T x, T y) {} + // called after combining all dp values of children + T fin(T x, int v) {} + + vector>> g; + vector ord, pae; + vector dp; + + T dfs(int v) { + ord.push_back(v); + for (auto [w, e] : g[v]) { + g[w].erase(find(all(g[w]), pair(v, e^1))); + pae[w] = e^1; + dp[v] = comb(dp[v], takeChild(dfs(w), e)); + } + return dp[v] = fin(dp[v], v); + } + + vector solve(int n, vector> edges) { + g.resize(n); + for (int i = 0; i < n-1; i++) { + g[edges[i].first].emplace_back(edges[i].second, 2*i); + g[edges[i].second].emplace_back(edges[i].first, 2*i+1); + } + pae.assign(n, -1); + dp.assign(n, E()); + dfs(0); + vector updp(n, E()), res(n, E()); + for (int v : ord) { + vector pref(sz(g[v])+1), suff(sz(g[v])+1); + if (v != 0) pref[0] = takeChild(updp[v], pae[v]); + for (int i = 0; i < sz(g[v]); i++){ + auto [u, w] = g[v][i]; + pref[i+1] = suff[i] = takeChild(dp[u], w); + pref[i+1] = comb(pref[i], pref[i+1]); + } + for (int i = sz(g[v])-1; i >= 0; i--) { + suff[i] = comb(suff[i], suff[i+1]); + } + for (int i = 0; i < sz(g[v]); i++) { + updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); + } + res[v] = fin(pref.back(), v); + } + return res; + } +}; -- cgit v1.2.3