| 题目名称 | 2478. [HZOI 2016] 简单的最近公共祖先 |
|---|---|
| 输入输出 | easy_LCA.in/out |
| 难度等级 | ★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Hzoi_
于2016-09-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：83， 提交：245， 通过率：33.88% | ||||
 WHZ0325 |
100 | 0.475 s | 27.03 MiB | C++ |
 APWTMECRD |
100 | 1.016 s | 31.76 MiB | C++ |
 烟雨 |
100 | 1.020 s | 31.76 MiB | C++ |
 lingyixiaoyao |
100 | 1.216 s | 12.01 MiB | C++ |
 HeHe |
100 | 1.299 s | 12.01 MiB | C++ |
 Soviets |
100 | 1.458 s | 30.80 MiB | C++ |
 Anonymity |
100 | 1.511 s | 27.02 MiB | C++ |
 QSZIO |
100 | 1.659 s | 47.62 MiB | C++ |
 Aptal丶 |
100 | 1.688 s | 42.25 MiB | C++ |
 Hzoi_Maple |
100 | 1.786 s | 38.46 MiB | C++ |
| 关于 简单的最近公共祖先 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
@GJ-shirry
结果却是树形DP。。。。 | ||||
|
……本想练习lca
 Shirry
2017-04-21 10:52
14楼
| ||||
|
回复 @Ezoi_HelenKeller :
节哀  AntiLeaf
2016-10-08 18:34
13楼
| ||||
|
VIP 发烧果然脑子都不好了...身败名裂
 沉迷学习的假的Keller
2016-10-08 18:22
12楼
| ||||
|
回复 @Satoshi :
话说你不是去美国了吗。。  asddddd
2016-10-08 18:19
11楼
| ||||
|
回复 @NewBee :
%%%跪求轻虐 AntiLeaf
2016-10-07 21:16
10楼
| ||||
|
回复 @Hzoi_AntiLeaf : % 拜 神犇 ～～～(请对号入座)
 Hzoi_Go灬Fire
2016-10-07 21:15
9楼
| ||||
|
| ||||
|
回复 @Hzoi_Go灬Fire :
十二门前融冷光，%拜神犇xzk AntiLeaf
2016-10-07 21:10
7楼
| ||||
|
%神犇@NewBee ，不加快读碾标程
| ||||
NewBee【题目描述】
给定一棵有n个节点的有根树，根节点为1，每个节点有一个权值$w_i$，求
即求所有无序节点对的LCA的权值之和。
树的节点编号为1~n，LCA表示两节点的最近公共祖先，即在它们的所有公共祖先中离根节点最远的节点。
【输入格式】
第一行一个整数n，表示节点数。
第二行n个正整数，表示每个点的权值。
以下n-1行每行两个整数x,y，表示树上有一条边连接节点x和节点y。
【输出格式】
一个整数，表示答案。
【样例输入】
3 1 2 3 1 2 1 3
【样例输出】
9
【数据范围与约定】
对于30%的数据，n<=1000。
对于60%的数据，n<=100000。
对于100%的数据，1<=n<=1000000，0<$w_i$<=1000000。
【来源】
HZOI 2016