洛谷P1351 - 联合权值

 OI / 洛谷
被浏览

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

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

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

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

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

枚举每个点,再枚举相邻的每条边,复杂度看似是 $O(n^2)$,但由于树的度数为 $n-1$,实际复杂度应为 $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
}