PrevNext
Rare
 0/8

(Optional) DP on Trees - Solving For All Roots

Authors: Benjamin Qi, Andi Qu, Andrew Wang

Tree DP that uses the subtree from excluding each node's subtree.

Focus Problem – read through this problem before continuing!

Solution - Tree Distances I

DFS twice. See CPH and the code for more details.

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4vector<int> graph[200001];
5pair<int, int> best[200001];
6int sec[200001], ans[200001];
7
8void dfs1(int node = 1, int parent = 0) {
9 for (int i : graph[node]) if (i != parent) {
10 dfs1(i, node);

Java

1import java.util.*;
2import java.io.*;
3
4public class Main {
5 public static ArrayList <Integer> g[];
6 public static Pair maxl1[];
7 public static Pair maxl2[];
8 public static void main(String[] args) throws Exception {
9 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
10 int N = Integer.parseInt(br.readLine());

Problems

Warning!

Although the intended solution for "Cow At Large" is extremely difficult, it is not too hard to fakesolve!

StatusSourceProblem NameDifficultyTagsSolution
ACNormal
Show Tags

DP

Balkan OINormal
Show Tags

DP, Functional Graph

GoldNormalExternal Sol
PlatHard
APIOHard
Show Tags

DP, Casework

External Sol
APIOVery Hard
Show Tags

DP, Casework

CEOIVery Hard
Show Tags

DP, Math

Check CF

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Module Progress:

Give Us Feedback on (Optional) DP on Trees - Solving For All Roots!

PrevNext