Add Dynamic Programming on Trees

[MCYang273730]

• Introduction to Dynamic Programming on Trees [1]

  • "Recursive" property of trees (very brief) [2]
  • Classic Example: CSES - Tree Matching [1] [3]
    • Defining a DP state
    • Implementation details
  • Classic Example: Finding the diameter and a center of a tree [4] [5] [6]
  • Exercise: AtCoder Educational DP Contest P - Independent Set [7]
  • Exercise: CSES - Finding a Centroid [8]
  • Exercise: NCPC 2021 NTHU preliminary problem G. Power Network [Reference?]
  • Exercise: Weighted version of some aforementioned problems (no judges known to me)
  • Non-classic Example: Codeforces Round 526 Div. 1 A. (== Div. 2 D.) The Fair Nut and the Best Path [9]
  • Non-classic Example: AtCoder Regular Contest 112 C - DFS Game [10]
  • Exercise: Codeforces Round 800 Div. 1 B. (== Div. 2 D.) Fake Plastic Trees [11]

• DP on Trees with Rerooting [12]

  • Preface: "Dynamic Programming" on Trees or "Divide and Conquer" on Trees? [2] [13]
  • Example: CSES - Tree Distances II [14]
  • Example: AtCoder Beginner Contest 223 G - Vertex Deletion [15]
  • Exercise: AtCoder Educational DP Contest V - Subtree [16]
  • Exercise: Codeforces Round 862 (Div. 2) D. A Wide, Wide Graph [17]

• DP on trees with $o(V)$ states

  • Example: Educational Codeforces Round 106 (Rated for Div. 2) F. Diameter Cuts [18]
    • Implementation: merging one subtree at a time
  • Exercise: Codeforces Round 833 (Div. 2) E. Yet Another Array Counting Problem [19]

• Related Topics
  (will use a few sentences to show how they are related, and links to other NTHU-CPP pages in the future)

  • LCA by Binary Lifting
  • Centroid Decomposition
  • Knapsack Problem on trees

• References

  • [1] https://usaco.guide/gold/dp-trees?lang=cpp
  • [2] https://tioj.ck.tp.edu.tw/uploads/attachment/11/54/7.pdf
  • [3] https://cses.fi/problemset/task/1130
  • [4] https://threadsiiithyderabad.quora.com/Dynamic-Programming-on-Trees-Tutorial/
  • [5] https://tioj.ck.tp.edu.tw/uploads/attachment/11/42/3.pdf
  • [6] https://mathworld.wolfram.com/GraphCenter.html
  • [7] https://atcoder.jp/contests/dp/tasks/dp_p
  • [8] https://cses.fi/problemset/task/2079
  • [9] https://codeforces.com/problemset/problem/1083/A
  • [10] https://atcoder.jp/contests/arc112/tasks/arc112_c
  • [11] https://codeforces.com/problemset/problem/1693/B
  • [12] https://usaco.guide/gold/all-roots?lang=cpp
  • [13] CLRS Introduction to Algorithms 3/e P. 384
  • [14] https://cses.fi/problemset/task/1133
  • [15] https://atcoder.jp/contests/abc223/tasks/abc223_g
  • [16] https://atcoder.jp/contests/dp/tasks/dp_v
  • [17] https://codeforces.com/problemset/problem/1805/D
  • [18] https://codeforces.com/problemset/problem/1499/F
  • [19] https://codeforces.com/problemset/problem/1748/E