QTREE
QTREE2 - Query on a tree II - solution
目录QTREE2 - Query on a tree II前置知识定义First. 求 \(dis_{u, v}\)Second. 求 \(u\) 到 \(v\) 路径上的第 \(k\) 个点时间复杂度Code QTREE2 - Query on a tree II \(\mathtt {TAGS} ......
QTREE2 - Query on a tree II - solution
目录QTREE2 - Query on a tree II前置知识定义First. 求 \(dis_{u, v}\)Second. 求 \(u\) 到 \(v\) 路径上的第 \(k\) 个点时间复杂度Code QTREE2 - Query on a tree II \(\mathtt {TAGS} ......
P4115 Qtree4 题解
P4115 看到单点修改，求全局白色的最远距离，可以使用点分树。 考虑维护这棵点分树，想想树的直径的 dp 求法：\(f_u = \max\{f_v + w(u, v)\}\)，答案为 \(\max(f_v+f_{v'})(v,v'\in \{\text{son}_u\})\)，\(\{\text{ ......
题解 QTREE7 - Query on a tree VII
题目描述 一棵树，每个点初始有个点权和颜色。 0 u ：询问所有 \(u,v\) 路径上的最大点权,要满足 \(u,v\) 路径上所有点的颜色都相同。 1 u ：反转 \(u\) 的颜色。 2 u w ：把 \(u\) 的点权改成 \(w\) 。 \(color_i\in[0,1]\)，\(w_i\ ......
Qtree3(树剖！！！)
[传送门](https://www.luogu.com.cn/problem/P4116) ## 前言 今天可以说是重新学了一下树剖吧，悄咪咪的打题，看了好久，纪念一下 ## 题目分析 题目很简单，就是一共两种操作： 1. `0 x` 把原来黑色的变成白色，白色的变成黑色 1. `1 x` 从 $1 ......
树链剖分 | 洛谷 P4114 Qtree1
给定一棵树，有修改边权和查询两点之间边权最大值两种操作，对于每个查询输出结果。
运用化边权为点权的思想，把边权转移到点上，并使用线段树维护最值。 ......