树链剖分 – Tgotp-Blog

3083: 遥远的国度

唔,没初始化 wa了一次…
思路很一眼。
就是说 考虑 树剖
如果 查询点是首都的祖先,那么查询点构成的子树就是 整个树除了 查询点包含 首都的儿子以外所有点。
那么 知道一个子树在树剖上是连续一段区间, 即 现在需要求 出 包含首都的那棵子树的根,
用类似倍增lca的方法即可。
对于查[......]

Read more

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 【模板】树链剖分

送一组简单数据。

模板没啥好说的吧。