QTREE
「SPOJ26374」QTREE5-LCT
· ✏️ 643 words · ☕ 2 mins read

你被给定一棵 $n$ 个点的树,点从 $1$ 到 $n$ 编号。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边个数。一开始所有的点都是黑色的。

要求作以下操作:

  • 0 i 将点 $i$ 的颜色反转(黑变白,白变黑)
  • 1 v 询问 $dist(u,v)$ 的最小值。$u$ 点必须为白色( $u$ 与 $v$ 可以相同),显然如果 $v$ 是白点,查询得到的值一定是 $0$ 。

特别地,如果作 1 操作时树上没有白点,输出 $-1$ 。


「SPOJ16580」QTREE7-LCT
· ✏️ 647 words · ☕ 2 mins read

一棵树,每个点初始有个点权和颜色(输入会给你)

  • 0 u : 询问所有 $u,v$ 路径上的最大点权,要满足 $u,v$ 路径上所有点的颜色都相同
  • 1 u : 反转 $u$ 的颜色
  • 2 u w :把 $u$ 的点权改成 $w$

「SPOJ16549」QTREE6-LCT
· ✏️ 698 words · ☕ 2 mins read

给你一棵 $n$ 个点的树,编号 $1$~$n$ 。每个点可以是黑色,可以是白色。初始时所有点都是黑色。有两种操作:

  • 0 u :询问有多少个节点 $v$ 满足路径 $u$ 到 $v$ 上所有节点(包括端点)都拥有相同的颜色
  • 1 u :翻转 $u$ 的颜色

「SPOJ913」QTREE2-LCT
· ✏️ 592 words · ☕ 2 mins read

给定一棵 $n$ 个点的树,边具有边权。要求作以下操作:

  • DIST a b 询问点 $a$ 至点 $b$ 路径上的边权之和

  • KTH a b k 询问点 $a$ 至点 $b$ 有向路径上的第k个点的编号

有多组测试数据,每组数据以 DONE 结尾。


「SPOJ375」QTREE1-LCT
· ✏️ 1045 words · ☕ 3 mins read

给定 $n$ 个点的树,边按输入顺序编号为 $1,2,…,n-1$,要求作以下操作:

  • CHANGE i v :将第 $i$ 条边权值改为 $v$
  • QUERY a b :询问从 $a$ 点到 $b$ 点路径上的最大边权

有多组测试数据,每组数据以 DONE 结尾。


「SPOJ2666」QTREE4-LCT
· ✏️ 1467 words · ☕ 3 mins read

你被给定一棵 $n$ 个点的带边权的树(边权可以为负)。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边权值之和。一开始所有的点都是白色的。

要求作以下操作:

  • C a 将点a的颜色反转(黑变白,白变黑)

  • A 询问 $dist(a,b)$ 的最大值。$a,b$ 点都必须为白色( $a$ 与 $b$ 可以相同),显然如果树上仍存在白点,查询得到的值一定是个非负数。
    特别地,如果进行 A 操作时树上没有白点,输出 They have disappeared.