Rare

0/9

# (Optional) DP on Trees - Solving For All Roots

Authors: Benjamin Qi, Andi Qu, Andrew Wang

### Prerequisites

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

Focus Problem – read through this problem before continuing!

## Solution - Tree Distances I

Resources | |||
---|---|---|---|

CPH |

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

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

implementation without checking whether `i == best[node].second`

C++

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

Java

import java.util.*;import java.io.*;public class Main {public static ArrayList <Integer> g[];public static Pair maxl1[];public static Pair maxl2[];public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));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! See the internal solution for details.

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

AC | Normal | ## Show TagsDP | ||||

Balkan OI | Normal | ## Show TagsDP, Functional Graph | ||||

Gold | Normal | External Sol | ||||

Plat | Hard | |||||

APIO | Hard | ## Show TagsDP, Casework | External Sol | |||

IZhO | Hard | ## Show TagsDP | View Solution | |||

APIO | Very Hard | ## Show TagsDP, Casework | ||||

CEOI | Very Hard | ## Show TagsDP, Math | Check CF |

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

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

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.