【题目来源】
洛谷：[P1351 NOIP 2014 提高组] 联合权值 - 洛谷
【题目描述】
无向连通图 \(G\) 有 \(n\) 个点，\(n−1\) 条边。点从 \(1\) 到 \(n\) 依次编号,编号为 \(i\) 的点的权值为 \(W_i\)，每条边的长度均为 \(1\)。图上两点 \((u,v)\) 的距离定义为 \(u\) 点到 \(v\) 点的最短距离。对于图 \(G\) 上的点对 \((u,v)\)，若它们的距离为 \(2\)，则它们之间会产生 \(W_v×W_u\) 的联合权值。
请问图 \(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
【算法标签】
《洛谷 P1351 联合权值》 #动态规划DP# #树形DP# #最近公共祖先LCA# #NOIP提高组# #2014#
【代码详解】
#include <bits/stdc++.h>
#define int long long
using namespace std;const int mod = 10007; // 模数// 定义节点结构体
struct Node
{int w; // 节点的权值vector<int> ve; // 存储相邻节点vector<int> wi; // 存储相邻节点的权值int sum; // 相邻节点权值之和int sub; // 相邻节点权值平方之和
} s[200005]; // 节点数组int n, u, v, maxx, ans; // n: 节点数, u,v: 临时变量, maxx: 最大乘积, ans: 计算结果signed main()
{// 输入节点数cin >> n;// 构建树结构，输入n-1条边for (int i = 1; i < n; i++){cin >> u >> v;s[u].ve.push_back(v); // 添加u的邻居vs[v].ve.push_back(u); // 添加v的邻居u}// 输入每个节点的权值for (int i = 1; i <= n; i++){cin >> s[i].w;}// 处理每个节点for (int i = 1; i <= n; i++){// 如果邻居数少于2，跳过（无法形成乘积）if (s[i].ve.size() < 2){continue;}// 遍历所有邻居节点for (int j = 0; j < s[i].ve.size(); j++){v = s[i].ve[j]; // 获取邻居节点s[i].wi.push_back(s[v].w); // 记录邻居节点的权值s[i].sum += s[v].w; // 累加邻居节点权值之和s[i].sub += s[v].w * s[v].w; // 累加邻居节点权值平方之和}// 计算并累加结果：使用公式 (sum)^2 - subans += s[i].sum * s[i].sum - s[i].sub;ans %= mod; // 取模// 对邻居节点权值排序sort(s[i].wi.begin(), s[i].wi.end());int len = s[i].wi.size() - 1;// 更新最大乘积（最大的两个权值相乘）maxx = max(maxx, s[i].wi[len] * s[i].wi[len - 1]);}// 输出最大乘积和计算结果cout << maxx << " " << ans << endl;return 0;
}
【运行结果】
5
1 2
2 3
3 4
4 5
1 5 2 3 10
20 74