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.
Prerequisites
Focus Problem – read through this problem before continuing!
View Internal SolutionSolution - Tree Distances I
Resources | ||||
---|---|---|---|---|
CPH |
Note
This problem previously appeared in Intro to Trees. This is simply 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 . The other DP array calculates results outside of the subtree rooted at .
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 as the maximum distance from node to any node in the subtree rooted at .
Define as the maximum distance from node to any node outside of the subtree rooted at .
Then the answer for node =
can be calculated using a DFS since = , where is a child of .
can also be calculated using a DFS as = , where and are both children of with .
To calculate in linear time, we can define another array such that is the second largest distance from node to any node in the subtree rooted at . So if is transitioned from the branch with , = . Otherwise = .
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 | |
---|---|---|---|---|---|
CF | Easy | Show TagsDP | |||
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 |