思想
与AcWing的1072树的最长路径很像,本题算的是最长点权路径。需要用不一样的写法。
代码
import java.util.Arrays;
import java.io.*;
import java.util.ArrayList;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 100010, ans = 0;
static ArrayList<Integer>[] tree = new ArrayList[N];
static int[][] f = new int[N][2]; //f[i][0]表示以i为根节点的树的最大子路径,f[i][1]表示以i为根节点的树的最大子路径与次长路径之和
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static void dfs(int u, int fa){
int d1 = 0, d2 = 0; //最长路径和次长路径
for(int i : tree[u]){
if(i==fa) continue;
dfs(i, u);
int d = f[i][0];
if(d>=d1){
d2 = d1;
d1 = d;
}
}
f[u][0] += d1;
f[u][1] += (d1+d2);
ans = Math.max(ans, f[u][1]);
}
public static void main(String[] args)throws IOException{
int n = nextInt();
//初始化
for(int i=1; i<=n; i++) tree[i] = new ArrayList<>();
for(int i=1; i<n; i++){
int a = nextInt(), b = nextInt();
tree[a].add(b); tree[b].add(a);
}
//将点权存储在路径上
for(int i=1; i<=n; i++){
int x = nextInt();
f[i][0] = f[i][1] = x;
}
dfs(1, -1);
out.println(ans);
out.flush();
out.close();
}
}