# DP on Trees - Solving For All Roots

Authors: Benjamin Qi, Andi Qu, Andrew Wang

Contributor: Dong Liu

Tree DP problems involving rerooting.

### Prerequisites

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution## Solution - Tree Distances I

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

CPH |

### Note

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

It is a common technique to calculate two DP arrays for some DP on trees problems. Usually one DP array is responsible for calculating results within the subtree rooted at $i$. The other DP array calculates results outside of the subtree rooted at $i$.

The focus problem asks us to find for each node the maximum distance to another node. We can divide the problem into two parts.

Define $f[x]$ as the maximum distance from node $x$ to any node in the subtree rooted at $x$, and $g[x]$ as the maximum distance from node $x$ to any node outside of the subtree rooted at $x$. Then the answer for node $x$ is $\max(f[x],g[x])$.

- $f[x]$ can be calculated using a DFS since $f[x]=\max(f[c])+1$, where $c$ is a child of $x$.
- $g[x]$ can also be calculated using a DFS as $g[c]=\max(g[x]+1, f[d]+2)$, where $c$ and $d$ are both children of $x$ with $c \neq d$.

To calculate $g$ in linear time, we can define another array $h$ such that $h[x]$ is the largest distance from node $x$ to any node in the subtree rooted at $x$ excluding the child subtree that contributed to $f[x]$. So if $f[x]$ is transitioned from the branch with $c$, $g[c]=\max(g[x]+1,h[x]+1)$. Otherwise $g[c]=\max(g[x]+1,f[x]+1)$.

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);

Java

import java.io.*;import java.util.*;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));

## Problems

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

CF | Easy | ## Show TagsDP | |||

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

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

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

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

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

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

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

Platinum | Very Hard | ## Show TagsDP, Tree |

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