题目
题目链接
题目大意：给出一棵 $n$ 个点的树，若树上两点 $u, v$ 满足距离为 $2$，则产生 $w_u \times w_v$ 的联合权值。求出树上最大的联合权值和所有联合权值的和。权值之和对 $10007$ 取余。$1 \le n \le 200000, 0 < w_i \le 10000$。
思路
（以前的暴力分好多啊）
考虑枚举离这两个点距离为 $1$ 的中间点，则只需要对每个点找出边连的点进行更新就行了。
最大值是很好求的，现在要求以这个点为中间点的所有权值之和。
不难发现 $(\sum w_i)^2 - \sum w_i^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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}
typedef long long LL;
typedef unsigned long long uLL;
const LL mod = 10007;
std::vector<int> g[200010];
LL w[200010];
LL ans, max;
int n;
int main() {
read(n);
for (int i = 1, u, v; i < n; ++i) {
read(u), read(v);
g[u].push_back(v), g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) read(w[i]);
for (int i = 1; i <= n; ++i) {
LL mx1 = 0, mx2 = 0, s = 0, sum = 0;
for (auto j : g[i]) {
if (w[j] > mx1) mx2 = mx1, mx1 = w[j];
else if (w[j] > mx2) mx2 = w[j];
}
max = std::max(max, mx1 * mx2);
for (auto j : g[i]) {
s += w[j];
s %= mod;
sum += (w[j] % mod) * (w[j] % mod);
sum %= mod;
}
ans += (s % mod) * (s % mod) - sum % mod;
ans %= mod;
}
printf("%lld %lld\n", max, ans);
}
|