| 题目名称 | 1963. [HAOI 2015]树上操作 |
|---|---|
| 输入输出 | haoi2015_t2.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-04-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：310， 提交：1081， 通过率：28.68% | ||||
 clearY |
100 | 0.350 s | 7.25 MiB | C++ |
 TAT |
100 | 0.402 s | 12.31 MiB | C++ |
 胡嘉兴 |
100 | 0.466 s | 10.81 MiB | C++ |
|
胡嘉兴 |
100 | 0.466 s | 11.95 MiB | C++ |
|
TAT |
100 | 0.551 s | 12.31 MiB | C++ |
 HtBest |
100 | 0.555 s | 14.05 MiB | C++ |
|
TAT |
100 | 0.571 s | 5.50 MiB | C++ |
 YGOI_真神名曰驴蛋蛋 |
100 | 0.578 s | 9.29 MiB | C++ |
 Hzoi_Hugh |
100 | 0.586 s | 5.27 MiB | C++ |
 hzoi_xx |
100 | 0.591 s | 11.00 MiB | C++ |
| 关于 树上操作 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
淼淼淼
| ||||
|
lazy下传写错多调了一个小时……
| ||||
|
有意思不？本人讲完课才会做这题……
恶心了我好几个月…… （其实是懒得写延迟标记）  HZOI_蒟蒻一只
2017-06-21 16:57
30楼
| ||||
|
long long
有句mmp不知当讲不当讲 | ||||
|
\(^o^)/~，好吧，要用到DFS序。。
| ||||
|
不想说啥了，一开始搞了个错的线段树的板子
| ||||
|
快读一定要读负数= =
一定要开long long= =  Hzoi_Mafia
2017-06-11 11:20
26楼
| ||||
|
| ||||
|
把几乎所有的int改为long long 后。。。过了。。。
 | ||||
|
写挂了之后重构，重构了一半对拍，终于找到线段树区间更改时的一个变量写错。。。
能说什么呢。。。 对拍保平安！！！ | ||||
┭┮﹏┭┮
Shirry
JustWB
Hzoi_Maple
BaDBoY
AntiLeaf
HeHe
kZime【题目描述】
有一棵点数为N的树，以点1为根，且树点有权值。然后有M个操作，分为三种：
操作1：把某个节点x的点权增加a。
操作2：把某个节点x为根的子树中所有点的点权都增加a。
操作3：询问某个节点x到根的路径中所有点的点权和。
【输入格式】
第一行两个整数N,M，表示点数和操作数。
接下来一行N个整数，表示树中节点的初始权值。
接下来N-1行每行两个正整数fr,to，表示该树中存在一条边(fr,to)。
再接下来M行，每行分别表示一次操作。其中第一个数表示该操作的种类（1~3），之后接这个操作的参数（x或者x a）。
【输出格式】
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
【样例输入】
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
【样例输出】
6
9
13
【提示】
对于30%的数据，N,M<=1000
对于50%的数据，N,M<=100000且数据随机。
对于100%的数据，N,M<=100000，且所有输入数据的绝对值都不会超过10^6。