题目描述
结论:找到树的一条直径的两个端点为p、q,那么对于树上的任意点,距离其最远的点一定是p或者 q,然后根据该结论做三次dfs,分别是求各点到根节点的距离(深度)、各点到直径上端点s1的距离以及各点到直径上端点s2的距离。最后遍历找最大价值。
代码
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 ArrayList<Integer>[] tree;
static int max; //max是直径的两个端点
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
//填充dis距离数组,u为当前节点,fa为父节点
public static void dfs(long[] dis, int u, int fa){
for(int i:tree[u]){
if(i==fa) continue;
dis[i] = dis[u]+1;
if(dis[i]>dis[max]) max = i; //结论:距离最远的点在直径的端点上
dfs(dis, i, u);
}
}
public static void main(String[] args)throws IOException{
int t = nextInt();
while(t-->0){
max = 0;
int n = nextInt(), k = nextInt(), c = nextInt();
tree = new ArrayList[n];
//将编号从0开始
for(int i=0; i<n; i++) tree[i] = new ArrayList<>();
for(int i=1; i<n; i++){
int u = nextInt()-1, v = nextInt()-1;
tree[u].add(v);
tree[v].add(u);
}
//开始确定每个点的深度
long[] depth = new long[n];
dfs(depth, 0, -1);
int s1 = max; //s1为树直径的一个端点
long[] d1 = new long[n];//所有点到端点s1的距离
dfs(d1, s1, -1);
int s2 = max; //s2为树的直径的另一个端点
long[] d2 = new long[n];//所有点到端点s2的距离
dfs(d2, s2, -1);
long ans = 0;
for(int i=0; i<n; i++){
ans = Math.max(ans, Math.max(d1[i], d2[i])*k-depth[i]*c);
}
out.println(ans);
}
out.flush();
out.close();
}
}