lca – Tgotp-Blog

送你一棵圣诞树

求一遍dfs序,然后对于两个同种相邻颜色的lca的id[x]-=1,

然后用树套树维护,用树状数组维护颜色,线段树维护区间权值和。

然后还要用一个set记录颜色的位置。

具体看代码、

(可读性“极佳”

c++代码如下:
[crayon-5b50a8a4685a8555[......]

Read more

2144: 跳跳棋

求lca神题。

手推一下会发现,对于一个点,有三种跳法:

即中间点向两边跳,两边点向中间跳。

设三元组(u,v,w)(u < v < w).

设a  = v - u,b = u - v.

不难发现,若 a < b ,则只能u向后跳,反之w向前跳。[......]

Read more