题目
题目描述
无向连通图G 有n 个点，n – 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i ，每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu
×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？
输入格式
输入文件名为link .in。
第一行包含1 个整数n 。
接下来n – 1 行，每行包含 2 个用空格隔开的正整数u 、v ，表示编号为 u 和编号为v 的点之间有边相连。
最后1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。
输出格式
输出文件名为link .out 。
输出共1 行，包含2 个整数，之间用一个空格隔开，依次为图G 上联合权值的最大值
和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007 取余。
「数据说明」
对于30% 的数据，1 < n≤ 100 ；
对于60% 的数据，1 < n≤ 2000；
对于100%的数据，1 < n≤ 200 , 000 ，0 < wi≤ 10, 000 。
输入样例
|
1 2 3 4 5 6 7 |
5 1 2 2 3 3 4 4 5 1 5 2 3 10 |
输出样例
|
1 2 |
20 74 |
题解
这道题其实是道水题（逃ε=ε=ε=┏(゜ロ゜;)┛
我们首先要发现的一点就是如果我们确定了一个点，他所遍历到的所有点它们互相的距离就是2。
所以我们就可以枚举每一个点，枚举它每一个可通往的点，最大值取
\(Mx=max(Mx,该点遍历的最大值\times该点遍历到的次大值)\)
而总和我们就取
Ans=\sum V[i] \times V[j]
i为遍历过的边 j为当前边
注意要最后答案要乘2，因为(1,3)(3,1)要算两次
代码
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int MAXN = 200004, mod = 10007; int Head[MAXN], Nt[MAXN * 2], to[MAXN * 2]; int tot, n; int v[MAXN]; int mx, ans; void add(int a, int b) { Nt[++tot] = Head[a]; to[tot] = b; Head[a] = tot; } void get(int x) { int sum = 0, ma = 0, m = 0;//当前总和，最大值，次大值 for (int i = Head[x]; i; i = Nt[i]) { if (v[to[i]]>ma) { m = ma; ma = v[to[i]]; } else if (v[to[i]]>m)m = v[to[i]]; ans = (ans + sum * v[to[i]]) % mod; sum = (sum + v[to[i]]) % mod; } mx= max(mx, ma*m); } int main() { cin >> n; for (int i = 1; i < n; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); add(b, a); } for (int i = 1; i <= n; i++) { scanf("%d", &v[i]); } for (int i = 1; i <= n; i++) { get(i); } cout << mx << " " << ans*2%mod << endl; return 0; } |