【题目来源】
AcWing：511. 联合权值 - AcWing题库
【题目描述】
无向连通图G有\(n\)个点，\(n-1\)条边。点从\(1\)到\(n\)依次编号，编号为\(i\)的点的权值为\(W_i\)，每条边的长度均为\(1\)。图上两点\((u, v)\)的距离定义为\(u\)点到\(v\)点的最短距离。对于图G上的点对\((u,v)\)，若它们的距离为\(2\)，则它们之间会产生\(W_u\times W_v\)的联合权值。
请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
【输入】
第一行包含\(1\)个整数 \(n\)。接下来\(n-1\)行，每行包含\(2\)个用空格隔开的正整数\(u,v\)，表示编号为\(u\)和编号为\(v\)的点之间有边相连。
最后\(1\)行，包含\(n\)个正整数，每两个正整数之间用一个空格隔开，其中第\(i\) 个整数表示图G上编号为\(i\)的点的权值为\(W_i\)。
【输出】
输出共\(1\)行，包含\(2\)个整数，之间用一个空格隔开，依次为图G上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对\(10007\)取余。
【输入样例】
5
1 2
2 3
3 4
4 5
1 5 2 3 10
【输出样例】
20 74
【解题思路】
【算法标签】
《AcWing 511 联合权值》 #DFS#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 200010, M = N * 2, mod = 10007; // 定义常量
int h[N], e[M], ne[M], w[N], idx; // 图的邻接表存储
int n; // 节点数量
int ans_max, ans_sum; // 存储最终结果// 添加边的函数
void add(int a, int x) {e[idx] = x; // 存储边的终点ne[idx] = h[a]; // 将新边插入到节点 a 的邻接表头部h[a] = idx++; // 更新节点 a 的邻接表头指针
}// 计算最大值和和的函数
void cal() {for (int u = 1; u <= n; u++) { // 遍历每个节点long long t1 = 0, t2 = 0; // t1 存储邻接节点权值和，t2 存储邻接节点权值平方和int max1 = 0, max2 = 0; // max1 和 max2 存储邻接节点权值的最大和次大值// 遍历节点 u 的所有邻接节点for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i]; // 邻接节点 jt1 += w[j]; // 累加邻接节点的权值t2 += w[j] * w[j]; // 累加邻接节点权值的平方// 更新最大值和次大值if (w[j] > max2) {if (w[j] > max1) {max2 = max1; // 原来的最大值变为次大值max1 = w[j]; // 更新最大值} else {max2 = w[j]; // 更新次大值}}}// 更新全局最大值ans_max = max(ans_max, max1 * max2);// 更新全局和，公式为 (t1 * t1 - t2) % modans_sum = (ans_sum + (t1 * t1 - t2) % mod) % mod;}
}int main() {memset(h, -1, sizeof(h)); // 初始化邻接表头指针为 -1cin >> n; // 读取节点数量// 读取边的信息并构建图for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b; // 读取边的两个端点add(a, b); // 添加边 a -> badd(b, a); // 添加边 b -> a}// 读取每个节点的权值for (int i = 1; i <= n; i++)cin >> w[i];// 计算最大值和和cal();// 输出结果cout << ans_max << " " << ans_sum;return 0;
}
【运行结果】
5
1 2
2 3
3 4
4 5
1 5 2 3 10
20 74