PrevNext
Rare
 0/10

DP on Trees - Solving For All Roots

Authors: Benjamin Qi, Andi Qu, Andrew Wang

Contributor: Dong Liu

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

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

View Internal Solution

Solution - Tree Distances I

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 ii. The other DP array calculates results outside of the subtree rooted at ii.

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]f[x] as the maximum distance from node xx to any node in the subtree rooted at xx, and g[x]g[x] as the maximum distance from node xx to any node outside of the subtree rooted at xx. Then the answer for node xx is max(f[x],g[x])\max(f[x],g[x]).

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

To calculate gg in linear time, we can define another array hh such that h[x]h[x] is the largest distance from node xx to any node in the subtree rooted at xx excluding the child subtree that contributed to f[x]f[x]. So if f[x]f[x] is transitioned from the branch with cc, g[c]=max(g[x]+1,h[x]+1)g[c]=\max(g[x]+1,h[x]+1). Otherwise g[c]=max(g[x]+1,f[x]+1)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);
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

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsDP
ACNormal
Show TagsDP
Balkan OINormal
Show TagsDP, Functional Graph
GoldNormal
Show TagsDP, Tree
APIOHard
Show TagsCasework, DP
IZhOHard
Show TagsDP
APIOVery Hard
Show TagsCasework, DP
CEOIVery Hard
Show TagsDP, Math
PlatVery 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!

PrevNext