洛谷P1351 - 联合权值

 OI / 洛谷
被浏览 次

由题意得一个点对的联合权值是它们的点权相乘，而 2 个点形成点对的条件是距离为 2。

于是我们可以通过枚举这 2 个节点的公共点来算出以这个点为中心的权值和。

但是先枚举中心点再枚举其相邻的节点时间复杂度达到了 O(n3)O(n^3)，我们不能承受。

经过观察发现，对于特定的点，它都要乘上除自己以外的所有点权，再相加。然后我们就可以先处理出点权和，统计答案的时候把自己减去即可。

虽然说题面里说是有序点对，但我们每次枚举的时候都定方向为当前点->其他点，所以最后也不需要再乘 2 了。

枚举每个点，再枚举相邻的每条边，复杂度看似是 O(n2)O(n^2)，但由于树的度数为 n−1n-1，实际复杂度应为 O(n+m)O(n+m)。

当然，这道题还有一个小小的坑点，题面里只说联合权值之和要取余，最大值却不需要取余，这个细节注意一下。

接下来上代码：

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
#include <cstdio>
#include <iostream>
using namespace std;
#define gc c = getchar()
int read() {
    int x = 0, f = 1;
    char gc;
    for (; !isdigit(c); gc)
        if (c == '-') f = -1;
    for (; isdigit(c); gc) x = x * 10 + c - '0';
    return x * f;
}
#undef gc
const int MAXN = 200005;
const int P = 10007;
int n, Ans, ans, a[MAXN];
int nedge, head[MAXN];
struct Edge {
    int to, nxt;
} edge[MAXN * 2];  // 边表2倍勿忘
void add(int x, int y) {
    edge[++nedge].to = y;
    edge[nedge].nxt = head[x];
    head[x] = nedge;
}
void calc(int k) {  // 关键函数
    int Max = 0, Maxx = 0, sum = 0;
    // Max为与k相连最大的点权值，Maxx为次大值
    for (int i = head[k]; i; i = edge[i].nxt) {
        int u = edge[i].to;
        if (a[u] > Max) {
            Maxx = Max;
            Max = a[u];
        } else if (a[u] > Maxx)
            Maxx = a[u];
        // 更新最大、次大值
        sum = (sum + a[u]) % P;  // 累加权值和
    }
    for (int i = head[k]; i; i = edge[i].nxt) {
        int u = edge[i].to;
        ans = (ans + (sum - a[u]) * a[u]) % P;
        // 当前点对答案的贡献为（除自己外总和）*（自己的权值）
    }
    Ans = max(Ans, Max * Maxx);
    // 当前公共点所能产生的最大联合权值为（最大值）*（次大值）
}
int main() {
    int n = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        add(x, y), add(y, x);
    }                                            // 前向星建边
    for (int i = 1; i <= n; i++) a[i] = read();  // 读入点权
    for (int i = 1; i <= n; i++) calc(i);        // 枚举每个公共点计算
    printf("%d %d", Ans, (ans + P) % P);
    // 因为我们在统计的时候是减一个数，所以可能会出现ans小于0的情况，要(ans+P)%P
}
 上一页