【每周三道题】【题解】提高题：联合权值

每周三道题

『每周三道题』是计蒜客信息学推出的周更栏目。每周，在我们都会在公众号上都会发布由简到难，共三道信息学题目，并于次日公布题解。欢迎各位同学积极踊跃地参与解题哟！

题解

这个题是求一棵树上，所有距离为 2 的点对的点权的乘积的和，以及所有距离为 2 的点对的点权的乘积的最大值。如果用暴力写，枚举中间点，那实际求的两个点一定是与这个中间点相连的，暴力枚举这两个点，会发现在一种特殊的情况下，所有点都和一个点相邻，复杂度就会达到平方，就会超时。

对于最大值，比较简单，在枚举中间点以后就可以直接取两个最大的相乘。

对于和，比较麻烦，可以这样优化，考虑如何快速计算以每个点为中间点的结果，会发现当枚举了其中一个点的时候，另一个点一定可以是中间点相连的除了已经枚举的那个点以外的所有点。所以可以在枚举中间点的基础上再枚举其中一个点，乘上其他与中间点相邻的点的权值和，这个权值和可以通过所有与中间点相邻的点的权值和减掉枚举的这个点的权值得到。

这样总复杂度降到了 O(n)。

标程

#include <cstdio>#include <iostream>#include <vector>using namespace std;const int mod = 10007;vector<int> G[200005]; // 邻接表int S[200005];int W[200005];int n, maxx, sum;int main() { cin >> n; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } for (int i = 1; i <= n; i++) { cin >> W[i]; } for (int i = 1; i <= n; i++) { int max1, max2; // 记录下与 i 相连的权值最大的两个点的权值 max1 = 0; max2 = 0; for (int j = 0; j < G[i].size(); j++) { S[i] = (S[i] + W[G[i][j]]) % mod; if (W[G[i][j]] >= max1) { // 更新最大值 max2 = max1; max1 = W[G[i][j]]; } else if (W[G[i][j]] > max2) { // 更新次大值 max2 = W[G[i][j]]; } } if (max1 * max2 > maxx) { maxx = max1 * max2; // 与之前求得的最大值取较大者 } } for (int i = 1; i <= n; i++) { // 枚举中间点 for (int j = 0; j < G[i].size(); j++) { // 枚举其中一个点 sum = (sum + (S[i] - W[G[i][j]]) * W[G[i][j]]) % mod; } } cout << maxx << ' ' << sum << endl; return 0;}