首页 > 试题广场 >

我永远喜欢珂朵莉

[编程题]我永远喜欢珂朵莉

我永远喜欢珂朵莉~！

但是......

给你一个n个点的以1为根的有根树，每个点点权为0，有m次操作。

每次操作有三个参数a,b,t

然后会给你a条链，把每条链上所有点权+1

然后会给你b个点，把每个点代表的子树里点权+1

对于每次操作，你需要输出点权>=t的点个数

每次操作是独立的，也就是说每次操作完之后所有点点权重新变成0



输入描述:
第一行二个数n,m
之后n-1行每行两个数x,y表示x和y直接连有边
之后m次操作
每次操作先是一行三个数a,b,t,意义已上述
之后a行每行两个数x,y表示一条从x到y的链上每个点点权+1
之后b行每行一个数x表示点x代表的子树内每个点点权+1


输出描述:
m行，第i行一个数表示第i次操作的答案
示例1

输入

5 2
1 2
2 3
3 4
4 5
1 1 2
2 3
3
1 2 2
1 3
2
5

输出

1
3

说明

示例2

输入

5 2
1 2
2 3
2 4
3 5
2 3 3
2 3
3 3
3
3
3
4 2 3
1 4
2 3
4 5
1 2
4
3

输出

2
3

说明

饶了我吧，图我是画不出来了GG
第一次操作：
点1,4值为0，点2值为1，点5值为3，点3值为5，有两个点值>=3，所以答案为2
第二次操作：
点1值为2，点2值为4，点3值为3，点4值为3，点5值为1，有三个点值>=3，所以答案为3

备注:
对于100%的数据，0 <= n <= 100000 , 0 <= m <= 400000 , 0 <= a的和<= 1500000 , 0 <= b的和<= 1000000
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

树状数组 离线算法
上传者：牛客301599号
难度：
0条回答 13浏览

热门推荐

通过挑战的用户

查看代码

相关试题

我永远喜欢珂朵莉

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号