PrevNext
Rare
 0/9

(Optional) DP on Trees - Solving For All Roots

Authors: Benjamin Qi, Andi Qu, Andrew Wang

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

Focus Problem – read through this problem before continuing!

Solution - Tree Distances I

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

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

implementation without checking whether i == best[node].second

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> graph[200001];
pair<int, int> best[200001];
int 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.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 NameDifficultyTagsSolutionURL
ACNormal
Show Tags

DP

Balkan OINormal
Show Tags

DP, Functional Graph

GoldNormalExternal Sol
PlatHard
APIOHard
Show Tags

DP, Casework

External Sol
IZhOHard
Show Tags

DP

View Solution
APIOVery Hard
Show Tags

DP, Casework

CEOIVery Hard
Show Tags

DP, Math

Check CF

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!

Give Us Feedback on (Optional) DP on Trees - Solving For All Roots!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext