GDOI模拟中，如何高效进行数树数操作？

本文共计828个文字，预计阅读时间需要4分钟。

描述一个由N个节点构成的树，节点编号从1到N。每个节点有一个权值。需要实现两种操作：1. 将节点i的权值变为x^2。2. 描述一棵由N个节点构成的树，节点编号从1到N。每个节点有一个权值。

Description给定一棵N个节点的树，标号从1~N。每个点有一个权值。要求维护两种操作：1.Cix(0x2^31)表示将i点权值变为x2.Q

Description

给定一棵N 个节点的树，标号从1~N。每个点有一个权值。要求维护两种操作： 1. C i x(0<=x<2^31) 表示将i 点权值变为x 2. Q i j x(0<=x<2^31) 表示询问i 到j 的路径上有多少个值为x 的节点

Solution

这是一道很裸的树链剖分的题目，有一道题很这题极其类似旅行 不过多了一些操作而已。

用动态开空间的方法

这种方法又快又好大，没有什么麻烦的操作，全是些基础。

要打个离散化加hash

我是一个c++选手，一个map就搞定了。