| 题目名称 | 1804. [NOIP 2014]联合权值 |
|---|---|
| 输入输出 | linkb.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2014-11-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：401， 提交：1612， 通过率：24.88% | ||||
 LGLJ |
100 | 0.071 s | 7.60 MiB | C++ |
 Youngsc |
100 | 0.089 s | 2.87 MiB | C++ |
 Hyoi_0Koto |
100 | 0.092 s | 2.56 MiB | C++ |
 GAOJINGCHAO |
100 | 0.097 s | 4.89 MiB | C++ |
 Hale |
100 | 0.099 s | 21.29 MiB | C++ |
 Furyton |
100 | 0.105 s | 1.96 MiB | C++ |
 lalalala |
100 | 0.108 s | 4.29 MiB | C++ |
 小e |
100 | 0.114 s | 4.30 MiB | C++ |
 铁策 |
100 | 0.116 s | 5.73 MiB | C++ |
 夜莺 |
100 | 0.118 s | 3.59 MiB | C++ |
| 本题关联比赛 | |||
| 近期练习题回顾 | |||
| 关于 联合权值 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
取余没看见被硬控了
| ||||
|
竟然线段树水过了，我一定是收到了天天爱跑步的影响QAQ
| ||||
|
数学优化(滑稽
| ||||
|
常数大了3倍。。。
| ||||
|
瞎j儿写
| ||||
|
回复 @FAQ :
cnm  逗比战士董哥
2017-07-14 15:40
32楼
| ||||
|
回复 @HZOI_蒟蒻一只 :
旁友，你的叹号太多了  +1s
2017-07-14 15:12
31楼
| ||||
|
千分留念！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 HZOI_蒟蒻一只
2017-06-10 18:40
30楼
| ||||
|
这一定是道数学题
  Hzoi_Mafia
2017-06-01 11:19
29楼
| ||||
|
。。。。。
| ||||
Hallmeow
snake
swttc
@@@
zhjian【题目描述】
无向连通图 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 的点的权值为 Wi 。
【输出格式】
输出共 1 行，包含 2 个整数，之间用一个空格隔开，依次为图 G 上联合权值的最大值和所有联合权值之和。对 由于所有联合权值之和可能很大，输出它时要对 10007 取余。
【样例输入】
5 1 2 2 3 3 4 4 5 1 5 2 3 10
【样例输出】
20 74
【样例说明】
本例输入的图如上所示，距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。其联合权值分别为 2、15、2、20、15、20。其中最大的是 20，总和为 74。
【数据规模与约定】
对于 30%的数据，$1<n\leq 100$；
对于 60%的数据，$1<n\leq 2000$；
对于 100%的数据，$1<n\leq 200,000, 0<Wi\leq 10,000$。
【来源】
在此键入。