「SCOI2015」情报传递-树链剖分-主席树

给定一个 $n$ 个节点的有根树,开始时每个节点的权值都为 $0$ 。一共有 $q$ 个时刻,每个时刻可能有如下两个操作之一:

  1. 给定一个节点 $x$ ,从下一个时刻起每个时刻都给该节点的权值 $+1$(每个节点只会有一次该操作);

  2. 给定两个节点 $x,y$ 以及一个数 $C$ ,求这两个节点的简单路径上权值大于 $C$ 的节点个数,以及简单路径上的所有节点个数。

「LNOI2014」LCA-树链剖分-差分

给出一个 $n$ 个节点的有根树。有 $q$ 次询问,每次询问给出 $l,r,z$ ,求 $\sum_{l \leq i \leq r}dep[LCA(i,z)]$ 。

「SDOI2014」旅行-树链剖分+动态开点线段树

给定一棵$n$个节点的树,对于每个点都有两个权值$w_i,c_i$。

存在$m$个操作,分为4类。

  • CC x c”:将$c_x$更改为$c$;

  • CW x w”:将$w_x$更改为$w$;

  • QS x y”:对所有满足在$x$到$y$路径上且$c_i = c_x = c_y$的节点$i$,求$\sum w_i$;

  • QM x y”:对所有满足在$x$到$y$路径上且$c_i = c_x = c_y$的节点$i$,求$\max(w_i)$;

对于后两个操作,保证$c_x = c_y$。

「NOI2015」软件包管理器-树链剖分

你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ,那么安装软件包 A 以前,必须先安装软件包 B 。同时,如果想要卸载软件包 B ,则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除 $0$ 号软件包以外,所有软件包都会依赖一个且仅一个软件包,而 $0$ 号软件包不依赖任何一个软件包。依赖关系不存在环。

现在有一些安装或卸载软件包的操作,需要求出这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包)。

「SDOI2011」染色-树链剖分+线段树

给定一棵有$n$个节点的无根树和$m$个操作,操作有$2$类:

  • 将节点$a$到节点$b$路径上所有点都染成颜色$c$;
  • 询问节点$a$到节点$b$路径上的颜色段数量(连续相同颜色被认为是同一段),
    如“$112221$”由3段组成:“$11$”、“$222$”和“$1$”。
    请你写一个程序依次完成这$m$个操作。

「ZJOI2008」树的统计-树链剖分

给定一颗 $n$ 个节点的树,节点编号为 $1$ 到 $n$ ,每个节点都有一个权值 $w_i$ 。

有以下三种操作或询问:

I. CHANGE u t : 把结点 $u$ 的权值改为 $t$

II. QMAX u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值

III. QSUM u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×