【题解】SPOJ QTREE* Query on a tree*

请注意,本文编写于 92 天前,最后修改于 92 天前,其中某些信息可能已经过时。

QTREE Query on a tree

Problem

给定一棵 $n$ 个节点的树,有边权
存在两种操作:

  1. 修改某条边的边权
  2. 求路径 $(a,b)$ 的最大边权

Thought

树链剖分即可

QTREE2 Query on a tree II

Problem

给定一棵 $n$ 个节点的树,有边权
存在两个操作:

  1. 求路径 $(x,y)$ 的长度
  2. 求有向路径 $(x,y)$ 上的第 $k$ 个点

Thought

树链剖分即可

QTREE3 Query on a tree again!

Problem

给定一棵 $n$ 个节点的树,每个点是黑色或者白色
存在两个操作:

  1. 将节点 $x$ 反色
  2. 求有向路径 $(1,x)$ 的路径上第一个黑色节点的编号

Thought

树链剖分即可

其实可以加强到任意两个节点路径上第一个黑色节点的编号

QTREE4 Query on a tree IV

Problem

给定一棵 $n$ 个节点的树,每个点是黑色或者白色,有边权
存在两个操作:

  1. 将节点 $x$ 反色
  2. 求路径 $(x,y)$ 的最大长度,要求 $x,y$ 均为白色

Thought

动态点分治入门

BZOJ 1095 [ZJOI2007]捉迷藏Hide

QTREE5 Query on a tree V

Problem

给定一棵 $n$ 个节点的树,每个点是黑色或者白色,有边权
存在两个操作:

  1. 将节点 $x$ 反色
  2. 求距离点 $u$ 最近的白点距离

Thought

动态点分治,维护每个白点到分治中心的距离
每次查询用 $\log n$ 的复杂度查询该点及点分树上的祖先

QTREE6 Query on a tree VI

Problem

给定一棵 $n$ 个节点的树,每个点是黑色或者白色
存在两个操作:

  1. 将节点 $x$ 反色
  2. 询问 $x$ 点同颜色联通块内的点数

Thought

有比较妙的做法:

将点变成边,边变为点

那么每次修改点的颜色相当于断开一条边
但是,我们仍然需要点来帮助我们维护答案,那么将原图中每个点的价值(其实就是1)放到新图上的点中,一般来说将其放到对应的边相连的点中较深的那个

这样,就可以用维护子树信息的 LCT 来维护每个点为根的子树中的联通块大小
注意到每个联通块的根节点其实可能颜色并不相同(白块,但是是带有黑点的权值),所以需要找到对应的儿子节点计算答案

QTREE7 Query on a tree VII

同 Query on a tree VI ,多维护一个路径上权值即可

Comments

添加新评论