旅游规划 树形DP DFS
🍑 算法题解专栏
🍑 旅游计划
输入
10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9
输出
0
1
2
3
4
5
6
8
9
🍑 树形DP：即在树上进行的 DP，由于树固有的递归性质，树形DP一般都是递归进行的。
🍑 树的直径：找到根节点下面的第一长和第二长的节点链 相加 即是树的直径
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
static int N = 200010;
static int M = 2 * N;
static int[] d1 = new int[N];// 记录每个节点往下走的最大长度
static int[] d2 = new int[N];// 记录每个节点往下走的次大长度
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx, ans, n;// ans 存树的直径
static boolean[] st = new boolean[N];
// 返回从节点 u 往下走的最大长度
private static int dfs1(int u, int fa)
{
int max1 = 0;
int max2 = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)// 以下犯上（非法）
continue;
int d = dfs1(j, u) + 1;
if (d > d1[u])
{
d2[u] = d1[u];
max2 = max1;
d1[u] = d;
max1 = j;
} else if (d > d2[u])
{
d2[u] = d;
max2 = j;
}
}
ans = Math.max(ans, d1[u] + d2[u]);
return d1[u];
}
// 从该点往下找最大长度
static void dfs2(int u)
{
st[u] = true;//边走边踩点
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
// 最大值
if (d1[u] == d1[j] + 1)
dfs2(j);
}
}
// 从该点往下找次大长度
static void dfs3(int u)
{
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
// 次大值
if (d2[u] == d1[j] + 1)//只要找了一次次大值，那剩下的都应该是最大值
dfs2(j);
}
}
static void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Arrays.fill(h, -1);
for (int i = 0; i < n - 1; i++)
{
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
add(b, a);
}
dfs1(0, -1);
for (int i = 0; i < n; i++)
{
if (d1[i] + d2[i] == ans)
{
dfs2(i);
dfs3(i);
}
}
for (int i = 0; i < n; i++)
if (st[i])
System.out.println(i);
}
}