联合权值

题目

无向连通图G 有n 个点,n - 1 条边。点从1 到n 依次编号,编号为 i 的点的权值为W i ,每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ,若它们的距离为2 ,则它们之间会产生Wu×Wv 的联合权值。

请问图G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

输入输出格式

输入格式:

第一行包含1 个整数n 。

接下来n - 1 行,每行包含 2 个用空格隔开的正整数u 、v ,表示编号为 u 和编号为v 的点之间有边相连。

最后1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。

输出格式:

输出共1 行,包含2 个整数,之间用一个空格隔开,依次为图G 上联合权值的最大值

和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007 取余。

输入输出样例

输入样例

5
1 2
2 3
3 4
4 5
1 5 2 3 10

输出样例

20 74

数据范围

对于30% 的数据,1<n≤100 ;

对于60% 的数据,1<n≤2000;

对于100%的数据,1<n≤200000,0<wi≤10000。

思路

最大的值一定是和一个点相连且是和这个点相连的点权值最大的两个点

我们就可以记录和一个点相连的最大和次大的两个点权值 然后取一个max

至于第二问 对于每一条边相连的两个点来说 其中一个点的对答案的贡献为 和另一个点相连的其它点的点权值之和 与 这个点的乘积

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
#include <iostream>
#include <cstdio>
#include <cmath>
#define N 200005
using namespace std;
const long long mod = 10007;
long long n, w[N], u[N][3], Max[N][3], v[N];
inline void update(long long x, long long y)
{
if (x > Max[y][0])
{
Max[y][1] = Max[y][0];
Max[y][0] = x;
}
else if (x > Max[y][1])
{
Max[y][1] = x;
}
}
int main()
{
// freopen("linkb.in","r",stdin); freopen("linkb.out","w",stdout);
scanf("%lld", &n);
for (long long i=1; i<n; i++) scanf("%lld%lld", &u[i][0], &u[i][1]);
for (long long i=1; i<=n; i++) scanf("%lld", &w[i]);
for (long long i=1; i<n; i++)
{
long long a = u[i][0], b = u[i][1];
v[a] += w[b]; v[b] += w[a];
update(w[a], b);
update(w[b], a);
}
long long Max_ans = 0, ans = 0;
for (long long i=1; i<=n; i++)
Max_ans = max(Max[i][1] * Max[i][0], Max_ans);
for (long long i=1; i<n; i++)
{
long long a = u[i][0], b = u[i][1];
ans += (v[a] - w[b]) * w[b] % mod; ans %= mod;
ans += (v[b] - w[a]) * w[a] % mod; ans %= mod;
}
printf("%lld %lld\n", Max_ans, ans);
return 0;
}