2014S_2：联合权值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/**************************************************************** 
 * Description: 2014年提高组第二题 联合权值 70分
 * Author: Alex Li
 * Date: 2024-10-11 17:18:25
 * LastEditTime: 2024-10-11 18:26:09
****************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 10007;

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    int n;
    cin >> n;

    vector<vector<int>> adj(n + 1); // 邻接表，节点编号从1开始
    vector<int> W(n + 1); // 节点权值，节点编号从1开始

    // 读入边，构建邻接表
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 读入节点权值
    for (int i = 1; i <= n; ++i) {
        cin >> W[i];
    }

    int max_joint_weight = 0; // 最大联合权值
    int total_sum = 0; // 所有联合权值之和

    // 遍历每一条边
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            if (u < v) { // 为了避免重复计算，每条边只处理一次（u < v）
                // 处理与边(u,v)相关的节点对

                // 遍历v的邻居，排除u
                for (int w : adj[v]) {
                    if (w != u) {
                        int joint_weight = W[u] * W[w];
                        total_sum = (total_sum + joint_weight) % MOD;
                        if (joint_weight > max_joint_weight) {
                            max_joint_weight = joint_weight;
                        }
                    }
                }

                // 遍历u的邻居，排除v
                for (int w : adj[u]) {
                    if (w != v) {
                        int joint_weight = W[v] * W[w];
                        total_sum = (total_sum + joint_weight) % MOD;
                        if (joint_weight > max_joint_weight) {
                            max_joint_weight = joint_weight;
                        }
                    }
                }
            }
        }
    }

    cout << max_joint_weight << " " << total_sum << endl;

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/**************************************************************** 
 * Description: 2014年提高组第二题 联合权值 100分
 * Author: Alex Li
 * Date: 2024-10-11 18:00:52
 * LastEditTime: 2024-10-11 18:05:29
****************************************************************/
#include <iostream>
using namespace std;

const int N = 2e5 + 5, MOD = 10007;

// 边结构体，表示从一个点到另一个点的连接关系
struct Edge {
    int to, next;
} edges[N * 2];

int head[N], edgeCount, values[N]; // head: 邻接表头节点索引, edgeCount: 边计数, values: 各点的权值
int n, totalWeightSum, x, y, maxPairWeight;

// 初始化邻接表，将边加入邻接表中
void addEdge(int u, int v) {
    edges[++edgeCount].to = v;
    edges[edgeCount].next = head[u];
    head[u] = edgeCount;
}

// 计算以某个节点为中转点的联合权值
void processNode(int u) {
    int sumOfNeighbors = 0;  // 记录邻居点的权值和
    int max1 = 0, max2 = 0;  // 记录邻居节点中最大的两个权值

    // 遍历当前节点 u 的所有邻居
    for (int k = head[u]; k; k = edges[k].next) {
        int neighborValue = values[edges[k].to]; // 获取邻居节点的权值

        // 动态更新两个最大的权值
        if (neighborValue > max1) {
            max2 = max1;
            max1 = neighborValue;
        } else if (neighborValue > max2) {
            max2 = neighborValue;
        }

        // 更新总的联合权值之和
        totalWeightSum = (totalWeightSum + sumOfNeighbors * neighborValue) % MOD;
        // 累加当前邻居的权值
        sumOfNeighbors = (sumOfNeighbors + neighborValue) % MOD;
    }

    // 更新最大联合权值，max1 和 max2 分别为当前节点邻居中最大的两个权值
    maxPairWeight = max(maxPairWeight, max1 * max2);
}

int main() {
    // 输入节点数
    cin >> n;

    // 输入边信息，建立无向图
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        addEdge(x, y);
        addEdge(y, x);
    }

    // 输入每个节点的权值
    for (int i = 1; i <= n; i++) {
        cin >> values[i];
    }

    // 枚举每个节点作为中转点，计算联合权值
    for (int i = 1; i <= n; i++) {
        processNode(i);
    }

    // 输出结果，最大联合权值和联合权值之和（后者需要乘以2并取模）
    cout << maxPairWeight << " " << (totalWeightSum * 2) % MOD << endl;

    return 0;
}