Rare
0/9
(Optional) DP on Trees - Solving For All Roots
Authors: Benjamin Qi, Andi Qu, Andrew Wang
Prerequisites
Tree DP that uses the subtree from excluding each node's subtree.
Focus Problem – read through this problem before continuing!
Solution - Tree Distances I
Resources | |||
---|---|---|---|
CPH |
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.
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
AC | Normal | Show TagsDP | ||||
Balkan OI | Normal | Show TagsDP, Functional Graph | ||||
Gold | Normal | External Sol | ||||
Plat | Hard | |||||
APIO | Hard | Show TagsDP, Casework | External Sol | |||
IZhO | Hard | Show TagsDP | View Solution | |||
APIO | Very Hard | Show TagsDP, Casework | ||||
CEOI | Very Hard | Show TagsDP, 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.