AcWing 1207. 大臣的旅费
原题链接
中等
作者:
两生
,
2023-01-11 17:58:07
,
所有人可见
,
阅读 151
Java-dfs
import java.io.*;
import java.util.*;
public class Main{
static class Edge{
int id, w;
public Edge(int id, int w){
this.id = id;
this.w = w;
}
}
static int N = 100010;
static List<Edge> h[] = new ArrayList[N];
static int dist[] = new int[N];
static int n;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine().trim());
for(int i = 0; i < n-1; i++){
StringTokenizer strInput = new StringTokenizer(br.readLine());
int p = Integer.parseInt(strInput.nextToken());
int q = Integer.parseInt(strInput.nextToken());
int d = Integer.parseInt(strInput.nextToken());
if(h[p] == null) h[p] = new ArrayList<>();
if(h[q] == null) h[q] = new ArrayList<>();
h[p].add(new Edge(q, d));
h[q].add(new Edge(p, d));
}
// 任取1节点,深搜记录所有距离1节点的距离dist[i]
dfs(1, -1, 0);
int u = 1; // 找到与1节点相距最远的节点,后续用该节点继续寻找与该节点相聚最远的节点,这两节点间的距离即为树的深度
for(int i = 1; i <= n; i++){
if(dist[i] > dist[u]) u = i;
}
// 第二次搜索,以u节点为根节点搜索距离u节点的最远节点,确定直径
dfs(u, -1, 0);
for(int i = 1; i <= n; i++){
if(dist[i] > dist[u]) u = i;
}
int s = dist[u]; // 此时的dist[u] 存储的即为最远距离
System.out.println(s*10 + s*(s+1l)/2); // 路费公式
br.close();
}
public static void dfs(int u, int father, int distance){
dist[u] = distance; // 记录每个直接相邻节点到初始指定节点的最大距离
for(Edge node : h[u]){
if(node.id != father){
// 因为更新的是与该节点直接相连的节点,并且只有该节点的父节点与该节点直接相邻,其父节点的父节点不与该节点直接相邻,所以不会存在父节点重复更新的情况
dfs(node.id, u, distance + node.w); // 继续搜索记录每个相邻节点距离初始节点的距离dist[u]
}
}
return;
}
}