Tag: LCA

5 篇文章

Luogu P3591 [POI2015]ODW 题解
Description 题目链接 给定一棵n个点的树,树上每条边的长度都为1,第i个点的权值为a[i]。Byteasar想要走遍这整棵树,他会按照某个1到n的全排列b走n-1次,第i次他会从b[i]点走到b[i+1]点,并且这一次的步伐大小为c[i]。对于一次行走,假设起点为x,终点为y,步伐为k,那么Byteasar会从x开始,每步往前走k步,如…
Luogu P1084 疫情控制 题解
Link Luogu Problem view Describe 有一棵以$1$为根节点的树,现在要在除根节点外的点设立阻拦,使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立,这$m$个军队中第$i$个一开始在点$q_i$上,军队移动的时间等于移动经过的边权之和,问最少要多少时间才能设立完阻拦。注意:不同的军队可以同时…
Codeforces Round #620 (Div. 2) 题解
Before Read Solve 4 of 7 Rank:1120 Rating Change:+29 1735 → 1764 Contest Link A. Two Rabbits Describe 两只可爱的兔子分别从$x,y$出发,相向而行,其中,左边的兔子一次跳$a$个单位,右边的兔子一次跳$b$个单位,数据保证$x<y$。 现有$…