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

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

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

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

Your browser is out-of-date!

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

×