树链剖分 – Tgotp-Blog

5210: 最大连通子块和

暂时拿了榜一…

观察这道题,很容易想到一个dp方程…
令f[i]表示i的子树与i相连最大联通块点权和 。。。
那么只要保证子树f[j] > 0那么一定可以加入f[i]当中。。。
那么现在就得到了所有的f值…
考虑答案实际就是在 i 的子树中所有节点的f值得max
然后就想到用树[......]

Read more

bzoj3626 LCA

首先,这是个好题

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

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

搞定。

c++代码如下:

 [......]

Read more

BZOJ4196: [Noi2015]软件包管理器

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

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

 

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

1036: [ZJOI2008]树的统计Count

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

P3384 【模板】树链剖分

送一组简单数据。

模板没啥好说的吧。