BZOJ 4999 LCA树状数组差分维护DFS序

时间：2018-06-06 19:15:12 阅读：212 评论：0 收藏：0 [点我收藏+]

Description

给一颗树，每个节点有个初始值

现在支持以下两种操作：

1. C i x(0<=x<2^31) 表示将i节点的值改为x

2. Q i j x(0<=x<2^31) 表示询问i节点到j节点的路径上有多少个值为x的节点

第一行有两个整数N,Q（1 ≤N≤ 100,000；1 ≤Q≤ 200,000），分别表示节点个数和操作个数

下面一行N个整数，表示初始时每个节点的初始值

接下来N-1行，每行两个整数x,y，表示x节点与y节点之间有边直接相连（描述一颗树）

接下来Q行，每行表示一个操作，操作的描述已经在题目描述中给出

对于每个Q输出单独一行表示所求的答案

解:

原文：https://www.cnblogs.com/Aragaki/p/9146575.html

踩

(0)

评论一句话评论（0）

分享档案

更多>