「SDOI2017」树点涂色-LCT+树链剖分

Bob 有一棵 $n​$ 个点的有根树,其中 $1​$ 号点是根节点。Bob 在每个节点上涂了颜色,并且每个点上的颜色不同。

定义一条路径的权值是,这条路径上的点(包括起点和终点)共有多少种不同的颜色。

Bob 可能会进行这几种操作:

  • 1 x,把点 $x$ 到根节点的路径上的所有的点染上一种没有用过的新颜色;
  • 2 x y,求 $x$ 到 $y$ 的路径的权值;
  • 3 x,在以 $x$ 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob 一共会进行 $m$ 次操作。

「CF68D」Half-decay tree-期望瞎搞题

定义一个完全二叉树树高为根节点到叶子节点经过的边数。

给定一个树高为 $h(1 \le h \le 30)$ 的完全二叉树,其中第 $x$ 个节点的左儿子为第 $2x$ 个节点,右儿子为第 $2x+1$ 个节点。

现在有 $q(1 \le q \le 10^{5})$ 个,分为两种操作:

  1. add v e ( $1 \le v \le 2^{h+1}-1,1 \le e \le 10^4$ )表示给第 $v$ 个节点的权值加 $e$
  2. decay 操作。我们在这个二叉树里面以等概率选择一个叶子节点,将这个叶子节点到根的路径上所有的边都删去。在删除后,树会形成若干个联通块,我们定义某个联通块的的权值为这个联通块内所有节点的权值之和。我们定义删除后的树的权值为形成的所有联通块的权值的最大值。请你求出这个值的期望。每次删除后会恢复所有删除的边。

「CF379F」New Year Tree-树的直径-倍增

你是一个程序猿,现在有一棵新年树(并不是传统的带着叶子的树)——它有四个节点: $1$ ,$2$ ,$3$ ,$4$ . 其中$2$ ,$3$ ,$4$ 的父亲都是 $1$ .

新年里,程序猿们往往会做一些有趣的事情。你则选择以往这棵树上加节点来取乐。 一个添加节点的操作是这样的:

  1. 找到树上的一个叶子结点 $v$ .
  2. 设现在树上有 $n$ 个节点,那么你现在会加入两个节点$n+1$ 和 $n+2$ ,它们都会成为 $v$ 的儿子.

你的任务是在做 $q$ 次这样的操作,并在每做完一次后计算一次树的直径。来吧,我们一起来解决这道新年问题吧!

「CF208E」Blood Cousins-线段树合并

给你一片森林,每次询问一个点与多少个点拥有共同的 $K$ 级祖先

「HEOI2016/TJOI2016」树-线段树

在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为 $1$),有以下两种操作:

  1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)

  2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先)

你能帮帮她吗?

「HNOI2014」世界树-虚树+树形dp

世界树的形态可以用一个数学模型来描述:世界树中有 $n$ 个种族,种族的编号分别从 $1$ 到 $n$,分别生活在编号为 $1$ 到 $n$ 的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为 $1$。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地 $a$ 和 $b$ 之间有道路,$b$ 和 $c$ 之间有道路,因为每条道路长度为 $1$ 而且又不可能出现环,所以 $a$ 与 $c$ 之间的距离为 $2$。

出于对公平的考虑,第 $i$ 年,世界树的国王需要授权 $m_i$ 个种族的聚居地为临时议事处。对于某个种族 $x$($x$ 为种族的编号),如果距离该种族最近的临时议事处为 $y$($y$ 为议事处所在聚居地的编号),则种族 $x$ 将接受 $y$ 议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则 $y$ 为其中编号最小的临时议事处)。

现在国王想知道,在 $q$ 年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。

「SHOI2014」概率充电器-树形dp

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器:

“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”

SHOI 概率充电器由 $n-1$ 条导线连通了 $n$ 个充电元件。进行充电时,每条导 线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率 决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排 了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

「SDOI2011」消耗战-虚树+树形dp

给定一个 $n$ 个点,以 $1$ 为根的有根树,砍断第 $i$ 条边的代价为 $c_i$。有 $m$ 次询问,每次给出 $k_i$ 个关键点(保证关键点不含 $1$ 号节点),询问能够使 $1$ 号节点不能到达任何关键点,所要砍断边的代价和最小是多少。

数据范围:$n,m \leq 250000,\sum {k_i} \leq 5 \times 10^5$

「ZJOI2012」网络-LCT

有一个无向图 $G$ ,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:

  • 对于任意节点连出去的边中,相同颜色的边不超过两条。
  • 图中不存在同色的环,同色的环指相同颜色的边构成的环。

在这个图上,你要支持以下三种操作:

  • 修改一个节点的权值。
  • 修改一条边的颜色。
  • 查询由颜色 $c$ 的边构成的图中, $u$ 到节点 $v$ 之间的简单路径上的节点的权值的最大值。

对于 100% 的数据,保证颜色不多于 $10$ 种。

「POI2011」Tree Rotations-线段树合并

现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 $n$ 个叶子节点,满足这些权值为 $1…n$ 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换,使得最终所有叶子节点的权值按照前序遍历序写出来,逆序对个数最少。

Your browser is out-of-date!

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

×