Rare

0/9

# DP on Trees - Solving For All Roots

Authors: Benjamin Qi, Andi Qu, Andrew Wang, Dong Liu

### 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 |

### Note

This problem previously appeared in Intro to Trees. This is simply an alternate solution to the problem.

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

C++

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

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

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

Gold | Normal | ## Show TagsDP, Tree | |||||||

Plat | Hard | ## Show TagsDP, Tree | |||||||

APIO | Hard | ## Show TagsCasework, DP | |||||||

IZhO | Hard | ## Show TagsDP | |||||||

APIO | Very Hard | ## Show TagsCasework, DP | |||||||

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

### 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!