标签: LCA

「ZJOI 2012」 灾难

阿米巴是小强的好朋友。

阿米巴和小强在草原上捉蚂蚱。小强突然想,如果蚂蚱被他们捉灭绝了,那么吃蚂蚱的小鸟就会饿死,而捕食小鸟的猛禽也会跟着灭绝,从而引发一系列的生态灾难。

学过生物的阿米巴告诉小强,草原是一个极其稳定的生态系统。如果蚂蚱灭绝了,小鸟照样可以吃别的虫子,所以一个物种的灭绝并不一定会引发重大的灾难。

「SCOI2015」情报传递

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 n 名情报员。每名情报员可能有若干名 (可能没有) 下线,除 1 名大头目外其余 n−1 名情报员有且仅有 1 名上线。奈特公司纪律森严,每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。

奈特公司每天会派发以下两种任务中的一个任务:

「16届同大邀请赛」 后花园的树

菜哭武的后花园里种着一棵树,这棵树有n个节点和n-1条边,每个节点都涂着一种颜色。菜哭武打算在接下来的m天里,每天执行以下两个操作之一:
1.菜哭武选择某一种颜色和树上的某一个节点,将这个节点涂上这种颜色(会将该节点原有的颜色覆盖)
2.菜哭武选择一种颜色,然后询问这棵树上所有涂着这种颜色的节点构成的子树含有多少个节点,(原树上的某个点集S构成的子树T的定义是:
如果u∈S,v∈S,那么原树u和v路径上的所有点都属于这棵子树T)。如果这棵树上没有这种颜色的节点,那么定义询问的结果为0。

「NOIP2015」运输计划

公元2044 年,人类进入了宇宙纪元。

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 uiu_i 号星球沿最快的宇航路径飞行到 viv_i 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tjt_j,并且任意两艘飞船之间不会产生任何干扰。

「Contest Hunter Round 56」 异象石

Adera是Microsoft应用商店中的一款解谜游戏。
异象石是进入Adera中异时空的引导物,在Adera的异时空中有一张地图。这张地图上有N个点,有N-1条双向边把它们连通起来。起初地图上没有任何异象石,在接下来的M个时刻中,每个时刻会发生以下三种类型的事件之一:

「BJWC2010」 严格次小生成树

小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:如果最小生成树选择的边集是EM,严格次小生成树选择的边集是ES,那么需要满足:(value(e)表示边e的权值)
sumeEMvalue(e)<eESvalue(e)sum_{e \in E_M} value(e) < \sum_{e \in E_S } value(e)

「BZOJ2144」 跳跳棋

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的
游戏:棋盘上有3颗棋子,分别在a,b,c这三个位置。我们要通过最少的跳动把他们的位置移动成x,y,z。(棋
子是没有区别的)跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只
允许跳过1颗棋子。