| 题目名称 | 2288. [HZOI 2015]疯狂的魔法树 |
|---|---|
| 输入输出 | H_Tree.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：17， 通过率：35.29% | ||||
 Aglove |
100 | 1.760 s | 9.25 MiB | C++ |
|
Aglove |
100 | 1.804 s | 14.04 MiB | C++ |
 assassain |
100 | 1.820 s | 14.04 MiB | C++ |
 stdafx.h |
100 | 1.929 s | 15.57 MiB | C++ |
 一個人的雨 |
100 | 2.022 s | 15.91 MiB | C++ |
|
stdafx.h |
100 | 5.401 s | 15.56 MiB | C++ |
|
Aglove |
80 | 1.040 s | 5.80 MiB | C++ |
|
Aglove |
60 | 9.103 s | 5.66 MiB | C++ |
|
stdafx.h |
50 | 10.056 s | 15.57 MiB | C++ |
|
stdafx.h |
30 | 0.617 s | 8.71 MiB | C++ |
| 关于 疯狂的魔法树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
题解报告戳http://www.cnblogs.com/joyouth/p/5440331.html
| ||||
【题目描述】
给定一棵有根树，树根为1
每个点有点权
要求你维护以下操作：
1、Q u a b 查询u子树中权值在a-b之间的点的个数
2、M u v 把u节点点权更改为v
3、C u v 把u子树所有点权值+v
4、W u v 把u子树所有点权值都变成v
5、A u v 增加一个新点，编号是当前节点总数+1，其父亲是u，权值为v
【输入格式】
第一行n，m 表示节点总数和操作总数
以下n个正整数表示每个点的点权
以下n-1行每行两个数u，v描述一条边的两个端点
以下m行每行一个操作 如题意所示
保证a<=b，n，m<=80000
【输出格式】
对于每个Q输出相应的答案
【样例输入】
输入：
20 20
11 14 20 7 17 19 11 18 13 6 19 10 6 11 20 2 8 5 13 15
2 1
3 2
4 2
5 3
6 2
7 2
8 3
9 2
10 2
11 3
12 3
13 5
14 2
15 4
16 7
17 16
18 15
19 18
20 15
W 20 20
A 13 19
Q 18 12 17
W 19 4
W 21 1
W 5 5
C 9 6
Q 15 3 19
W 12 19
C 12 5
W 12 7
W 10 16
C 6 9
W 4 2
W 12 8
W 14 10
Q 10 2 9
W 1 21
W 19 9
C 13 1
【样例输出】
1
2
0
【提示】
为了卡住暴力，前5个测试点的树形态是随机的
而后5个测试点设某个点为i，则其父亲的编号在[i-20,i-1]之间