Tree(点分治)

Tree

对问题的分析设计过程

该题要求求出树上路径长度$\leq K$的路径总数,为点分治经典题目

程序中用到的数据机构和算法

程序使用点分治实现,点分治的思想为将一颗树通过重心分割成多棵树来分治求解。即答案=路径通过重心的合法数目+子树答案。求解路径通过重心的合法数目可以通过容斥原理在$O(n\log n)$的时间内得出,可以证明,在用重心进行分割的前提下,时间复杂度为$O(n\log^2 n)$

程序的运行情况

该程序提交了两次才通过,具体情况如下:

321509264477_.pic

311509264471_.pic

在实习过程中得到的经验和体会

要对程序的初始值有足够的细心

Code:

 

HNOI2015 Day 2题解

昨天做了HNOI day 2,感觉好像还是可做的,想当年什么splay还是高级算法,现在点剖什么就老考了简直丧病,虽然第二题还没写那就先当下嘴巴选手吧= =

T1:[HNOI2015]落忆枫音

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4011

这道题还是挺神奇的,首先如果是个DAG的话我们可以把所有点的入度相乘就得到答案。

那么现在加上了一条边x->y,也就是说答案=原来的答案+用上这条边的答案,

我们可以发现,如果我们把x到根的链拿出来,其他点其实和DAG图上一样也可以入度直接相乘而得到答案,也就是S/prod(in[x])x为链上的点,可以发现如果记f[x]为所以到x的链上的1/prod(in[x])(也就是逆元啦)之和,我们可以用拓扑序来进行dp维护,就可以解决本题啦

我打的有点复杂,我是先把整个图的入度相乘然后再删去不合法的情况,也就是找y->x的链上的1/prod(in[x])之和,比较难打,但是总体思想差不多也就这样啦。

CODE:

View Code

 

T2:[HNOI2015]开店

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4012

又是CLJ的神题,数据结构一般都是被很多数据结构大神用各种方法秒,吾等蒟蒻只能被秒了= =

解法一:

首先有一种比较高端的做法,就是用线段树那样维护虚树,每个节点维护l~r的虚树(一共log n层每次直接nlogn暴力重构一共O(n log^2 n)),那么求答案可以在每棵虚数中单独求解。

接下来我们考虑如何求答案。对虚树上的节点分别记录子树中点的距离和down,子树外点的距离和up,以及子树中的节点数size。对于每一个查询,我们先找到在dfs序中比他前的点以及比他后的点,选择lca深度较大的点进行转移(因为这样才不会影响答案)。记从点x转移到点y,那么答案为down+up+(dist[y]-dist[x])size-(dist[y]-dist[x])(tot-size)(dist为该点的深度,tot为总节点树)

解法二:

我们可以先点剖一下然后考虑用可持久化线段树维护,对于每个点他至多被log n个重心覆盖,我们分别对每个重心ai进行查询,要求路径x,y必须穿过重心ai,记i的子树中l~r的节点数为count[i],dist[u]为u到重心的距离,sum[i]表示i子树中l~r的节点的dist之和,那么该子树ai的答案为count[ai]dist[u]+sum[x]-count[y]dis[u]-sum[y], 其中y为包含u的x的儿子节点,那么我们只需对重心已经他们的儿子节点维护一个线段树即可。

但是这样会爆空间,注意到每个点的儿子最多只有3个,那么我们可以直接维护他的儿子节点,不用维护其儿子节点即可

UPD:其实不用线段树的= =,开个vector记录子树节点然后排下序用前缀和,然后每次二分查询就行,感觉特别STL,初始化部分之间可以照搬CLJ ZJOI2015幻想乡战略游戏,几乎一模一样,写完不用3kb= =

两种做法时间均为O(N log^2 N)

CODE:

View Code

 

T3:[HNOI2015]实验比较

描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4013

首先对于这道题,我们可以发现如果u=v,那么我们可以将其两个点缩为同一个点,若u<v,那么我们可以连一条u向v的边,可以证明最后的图上每个联通块一定是一个环或者树。

如果是一个环的话答案显然为零。如果是一棵树的话,我们考虑使用树形dp,如果我们已知所有子树的答案,如何更新这棵树。

观察一个序列,我们可以发现该序列总是被若干个<分割成若干块,那么我们可以记f[i][j]为以i 为根节点的子树序列中有j个块的方案数一共有多少种,可得对两个不相干的树x,y结合的话,记答案为g[k],可得f[x][i],f[y][j]对g[k]的贡献为C(k,i)C(i,i+j-k)f[x][i]*f[y][j](可以这样认为,i个人先占据i个方格,那么剩下k-i个方格必须由j个人去占领,所以最后i+j-k个人就必须与之前的i个人一起了)

每次更新的时间复杂度为O(n^3),总的时间复杂度为O(n^4),可以通过这道题

CODE:

View Code

 

BZOJ 3924: [Zjoi2015]幻想乡战略游戏(动态点分治)

这种动态点分治嘛,GDKOI时听打到了,也有同学讲到了,所以印象比较深刻也就想出来了,然后就在实现方面卡了好久= =

不得不说CLJ说得真的太简单了,实现方面根本没提。

首先我们可以先用树分治构建出这棵树的分治树,也就是把这棵树的重心作为根节点然后子树为他的子树的重心这样递归下去,然后每个节点存的是其子树的信息。

对于每个节点我们保存这个子树的dv的总和已经把该节点作为点的答案值

这样对于修改能在log n的时间内解决

寻找答案的时候,我们可以发现,如果现在节点的子树dv和*2大于总节点,那么向那个方向过去一定比原方案好

我们先从根节点开始,若发现答案在某棵子树时,我们考虑如何使其儿子节点的答案转变为整个树的答案,可以发现把除这个子树外的所有节点可以缩成一个节点并连在这棵子树上,然后就可以一直这样做下去,找到操作之后再把这些撤销

因此还是得维护一些奇奇怪怪的东西,但打出来还是挺短的

Code: