这个题目相当经典了，是一个树结构的询问题。一般而言，这种题目都是先给出一个树，然后进行更改边权值、对边的修改（节点也可以），然后对某段路径进行询问。从根本上来讲，这类题目的本质都是在维护树的路径。

QTREE算是这类题目中的一道入门题。给出一棵树，然后更改边的权值或者询问一条路径上边权最大的边。由于不涉及树的形态，我们直接用树链剖分先构造固定的线段树来维护路径。对于相应的更改和询问，只要先预处理好LCA就可以轻松维护了。

在树中不同路径中遍历的复杂度是O(log n)，查询一次边的复杂度是O(log n)，每次查询LCA的复杂度是O(log n)。我在预处理LCA的时候采用的是O(n log n)-O(log n)的算法，所以总的复杂度就是O(n log n+q log² n)。事实上，如果我们用RMQ的O(n)-O(1)算法来处理这个LCA，复杂度就应该是O(n+qlog² n)。

值得注意的是，使用gets()优化一下输入，程序会快很多，我的程序就快了1.37s。至于为什么我的程序这么慢，只能说明我的代码写得太烂了。

Your program in C++ from 2010-04-07 07:19:34 ran for 4.09 seconds and used 4424 KB of memory.

Your program in C++ from 2010-04-07 11:05:42 ran for 2.72 seconds and used 4348 KB of memory.

• Relative Posts