树链剖分 – Tgotp-Blog

bzoj3626 LCA

首先,这是个好题

观察,发现对与lca(i,z)可以转换为i到根的距离与z到根的距离权值和;

转换一下,从 1 – n开始,然后从1-n开始插入,统计(运用差分的思想。

搞定。

c++代码如下:

&nbsp[……]

Read more

BZOJ4196: [Noi2015]软件包管理器

算是做了一道noi真题,这题很水,如果不会的话可以先做下洛谷的树链剖分模板(这题比这题难233)。

话说我代码就别往洛谷的贴, 洛谷此题有毒,你过不去的2333、

 

2017年7月4日 BZOJ4196: [Noi2015]软件包管理器已关闭评论 / /

1036: [ZJOI2008]树的统计Count

典型的树链剖分,就是一道模型题。

P3384 【模板】树链剖分

送一组简单数据。

模板没啥好说的吧。