PrevNext
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.

Tree Distances I
CSES - Easy

Focus Problem – read through this problem before continuing!

Solution - Tree Distances I

Resources
CPH
14.3 - All Longest Paths

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.

StatusSourceProblem NameDifficultyTags
AC
Subtree
Normal
Show TagsDP
Balkan OI
2017 - City Attractions
Normal
Show TagsDP, Functional Graph
Gold
Directory Traversal
Normal
Show TagsDP, Tree
Plat
Cow At Large
Hard
Show TagsDP, Tree
APIO
2010 - Patrol
Hard
Show TagsCasework, DP
IZhO
2017 - Hard route
Hard
Show TagsDP
APIO
2014 - Beads
Very Hard
Show TagsCasework, DP
CEOI
2020 - Star Trek
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!

Join Forum
PrevNext