树的重心有这些性质

树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
一棵树最多有两个重心，且相邻。

P4299 首都

对于这样一道动态树的重心题,我们应该选择哪个性质下手呢?

如果选择3

考虑启发式合并的过程,每次我们把小的向大的集合里并,一个点一个点的加入进去

然后会发现,如果link完之后x所在的子树超过了总点数大小的一般,就向x方向爬一步,维护这个x所在子树,可以考虑splitx,重心,然后重心左边第一个点就是这个方向上的第一个点,同时维护这个点的真实siz大小就能够知道子树大小了

然后这个复杂度是 $O(nlog^2n)$ 坏了

如果选择2和1

也就是说重心只会在一条链中出现,而且这条链就是原来的两个重心的路径

那么根据重心的调整法性质:每次向大的一个方向跳,我们就可以想办法二分了

splay本身就是二叉搜索树,考虑树上二分,设lsum为左儿子以及他们虚树的siz和,rsum为右儿子,以及他们的虚树的siz和

然后考虑lsum+sizL和rsum+sizR谁大,就向谁跳一步,并且将另一个加上siz值qwq

然后如果lsum和rsum都满足小于总树大小的一半,说明我们找到了,再去考虑是不是可能只有一个重心,因为如果有多个重心还要再挪移一步,找到那个重心,二者编号取min

如果点数为奇数,则不可能有两个重心

关键部分code:

inline int update(R x){
    R l,r,ji=s[x]&1,sum=s[x]>>1,lsum=0,rsum=0,newp=INF,nowl,nowr;
    while(x){
        pushdown(x);//注意pushdown
        nowl=s[l=lc]+lsum;nowr=s[r=rc]+rsum;
        if(nowl<=sum&&nowr<=sum){
            if(ji){newp=x;break;}//剪枝，确定已经直接找到
            else if(newp>x)newp=x;//选编号最小的
        }
        if(nowl<nowr)lsum+=s[l]+si[x]+1,x=r;
        else         rsum+=s[r]+si[x]+1,x=l;//缩小搜索区间
    }
    splay(newp);//保证复杂度
    return newp;
}

P3703 [SDOI2017]树点涂色

LCT做法:

非常玄妙

观察下splay

设dis[x]为x走到根的经过的颜色个数

我们发现,如果一开始所有点连接的都是虚边,一个点到根的路径经过的虚边个数+1正好就是这个点的dis值!

而且!操作1,对应了把点u到根的路径打通,即 $access(u)$

操作一遍后,你会发现如果还能按照LCT的结构维护这个dis数组,正好答案就是对的,我们只需要考虑 $access$ 的变化

不难发现我们还要一棵线段树按照dfn序维护这个dis数组

那么当access的时候,会有右儿子变虚,并且x变重的过程

那么那个右儿子对应的子树的dis值都会增加,而x的子树对应的dis值都减少qwq,一整个子树,所以对应dfs序上连续一段区间可以直接区间修改

然鹅,我们发现LCT这个坏家伙维护的是实链的中序遍历,而不是这个原树的真实信息....

所以我们要在对应的链一直跳右儿子,找到那个深度最浅的节点,在那上面的子树区间修改

同时不难发现我们操作2等价于查询LCA进行 $dis_x+dis_y-2dis_{lca}+1$

你可能会疑惑我们会有把颜色算重的情况,但是LCT的形态做的就是消除算重影响这样一件事情啊!

树剖做法:

你发现LCT对的原因就是均摊复杂度是 $O(nlogn)$ 的

所以说我们维护一下区间同色段,每次跳重链的时候向上一次改一整个同色段,并改掉他们的影响就好了....qwq

区间同色段这个东西....看上去就很线段树二分是吧?再根据均摊理论,我们应该有改掉一次同色段花费log,而最多增加一个异色段qwq

P4332 [SHOI2014]三叉神经树

思路并不难哎应该说比之前rqy?的题要简单许多

你会发现我们改了之后,假设是0改成1吧

一定只会影响到根最长的一段满足是001的节点,他们都会改成011的状态

同时这条链上的父亲节点也可能被改变

那么怎么维护呢?考虑LCT,树剖?5e5啊

把u $access$ 上去然后 $splay$ 到根,再考虑再splay上二分

具体的,我们先跳u的左子节点,然后判断右节点时候都是状态001的话,我们就直接给整个右子树打个修改为状态011的标记,然后再走左子树

否则说明我们在右子树就能停下来啦,就直接递归进入右子树,找到这个点

注意我们要修改这条链上面那个点,不妨我们最后停在点u,他的前驱就是我们的父亲呐

P5212 SubString

P6292 区间本质不同子串个数

~~真的有区间SAM啊~~

考虑扫描线,就是从左到右扫描过去,然后比如 $[l_1,r]$ 对应的上一个出现的本质不同的子串删除掉,然后再在线段树的 $l_1$ 位置加上

但是这道题并不能这样做,因为本质不同的子串可以达到 $字符集*n$ 的级别,而且他们出现的次数显然是 $n^2$ 级别的QAQ

也就是说上述复杂度是 $n^2logn$ 还不如区间SAM暴力建

考虑我们每次实际上具体用SAM找出那些子串是新的时候,我们要向找到u(1~i前缀对应的节点),然后再在u开始跳后缀树,跳过的所有节点代表的串全部都需要更改一遍

所以说SAM一个儿子到根要更改的只是一条链的代表的子串的信息,而我们再仔细思考,这样的信息,从一个节点到父亲的边上,代表的子串应该是长度连续的,也就是说是序列上连续的一段子串

而如果我们把这个操作看成将i到根的路径颜色变为一个新颜色的话,就等价于之前那道题的LCTaccess操作:我们每次经过一个splay的时候,将这个splay的信息暴力的 $logn$ 更改一下,然后继续向上access即可,你会发现每次我们更改颜色不需要对于一整个endpos等价类位置的串变换,只需要变换上一次的颜色那个位置即可

因此每次操作都能变成区间加等差数列,因为我们的影响都是一段连续的区间,也就做完了!

注意,我们这个LCT不能到处access还是只能在需要的时候才动他

P6385 『MdOI R2』Little Goth

$n-(R-L+i)+(L-k)=n-R+L-i+L-k=2L-R-k-i+n$

结论-1所有合法的j,选取最大的作为小B的起始位置一定不劣

显然

结论0加入当前有i=j,那之后一直保持i=j一定不劣

显然,如果我们分开了,就算是为了3,我们也有一个字符匹配成功的情况

结论1存在一种方案,使得在进行一次操作3时,操作串不是给定 $S_{i...j}$ 的子串且优于一切不是这样的方案,那么这个方案一定不优于先让 $i=j$ ,再进行操作

因为操作之后我们要么让 $i-1$ 要么让 $j+1$ 了

但是你会发现,操作3之后你一定是向着k的方向动过去的,所以你可以考虑操作3前也直接移动到k位置的方向,然后再进行操作3

那么,如果 $i>k$ ,显然我们可以j向i方向跳,然后跳到一起,再在i+?位置进行同样的传送

如果 $i<k$ ,显然我们可以i向j的方向跳,然后再进行j-?位置处进行同样的传送

两个都不会更劣,就相当于调整了操作顺序而已

不使用操作3,答案是 $|i-k|$

使用操作3,考虑只是单字符的case,就是一个标准的最短路算法

$dis_{i,x}$ 表示从i开始的到达任意一个字符为x的点最小代价,那可以考虑从所有字符为x的点开始多源最短路,显然可以通过每个字符建立一个虚点来实现优化建图

回答询问的时候考虑i,j合并到某一个字符,然后再走到这个k处即

$j-i+min(dis_{i,x},dis_{j,x})+dis_{k,x}+1$

那么我们只需要考虑操作3是 $S_{i...j}$ 的子串的case了!

结论1-2一定能有一种操作序列是向进行12再进行3再进行操作1

加入操作之后i的位置为p

因为如果 $p<k$ 你会发现此时一定可以平移到i=j然后再移动过去即可!

第二种case是 $p>k$ 加入操作后得到的是 $[L,R]$ 我们有答案是开头那个式子呢!

所以你会发现我们只需要最小化 $2L-R$

暴力1

枚举这个L,然后考虑最大化R

二分这个R即可,然后倍增定位这个 $S_{L..R}$ 对应的串

然后观察这个串对应的 $endpos$ 是否有存在于 $[i+R-L,j]$

$endpos$ 需要线段树合并?不,你想想可爱的LCT以及上个题就会怎么LCT做了

如果有,说明合法呢然后这样我们就得到一个 $O(nlog^2n+qnlogn)$

暴力2

固定长度,有固定的 $R-L$ ,那么我们尽量小这个L,就能尽量小这个答案

不妨固定这个k,那么我们可以计算出每个节点代表子串在k之后出现的最早位置,在endpos上找即可,记其为 $g_i$

$f_i=\min(f_{fa_i},f_{link_i},g_i-len_i-1)$

其中 $fa_i$ 是后缀树上父亲的节点,对应了删除一个后缀的信息

$link_i$ 是后缀树上的后缀连接,对应个删除一个前缀的信息

为什么-1我也不知道💢

正解

考虑用两个暴力均摊这个复杂度

我们再仔细看看,一个询问有 $i,p,k$ 三个变量

第一个暴力有:枚举一个 $L>k$ ,然后你会发现只需要判断 $i,j$ 的等价类有没有这个,也就是说每次 $i$ 发生变换都要重新跑一遍,但复杂度只和k相关

那么可以直接对于k分块后一段内暴力修改,这部分复杂度是 $O(qBlog)$

第二个暴力有,在后缀树上做一个dp,对于一个固定的k,我们能得到所有的i,j串的信息,同时得到的类似于第一个暴力中的信息,复杂度在于n

那么我们对于k分块后,每次对于端点跑一个这个暴力dp,这部分复杂度是 $O(\frac{n}{B}*n)$

故B取 $\sqrt{\frac{n}{logn}}$ 最优秀,前部分复杂度为 $q\sqrt{nlogn}$ ,后部分复杂为 $n\sqrt{nlogn}$

故本题做完啦!真不戳!

补充:SAM一点点性质

后缀链接

是对于v这个等价类对应的所有串中最长的串w,将w不断取他的后缀,直到那个后缀的endpos和v不再相同时得到的等价类,这两个在fail树上的节点相连的一条边

endpos等价类要么不交要么包含

一个endpos等价类会包含长度连续的一段子串

便于理解本题

P4338 [ZJOI2018]历史

给出一棵树,给定每一个点的accessaccessaccess次数,计算轻重链切换次数的最大值,带修改.

dfs一遍的很简单把

就是你考虑每个点的所有子树access的次数,如果有一个超过了一半,就说明我们达不到卡满的上界了

$2maxf_v\leq f_i+1$ 这样能卡满 $f_i-1$ ,否则只有 $2(f_i-f_v)$

然后考虑钦点实边连接那些点权是超过一半的,否则就是虚边

修改的时候,如果这个点上面本身就是的那些是没有意义的,答案不会变

只有虚边所以你会发现每次access相当于打通一些虚边,当然可能不打通到根

在access的过程特判一下就好了,然后改变他们的答案

因为我们每次会改变一条链,所以要用注意特判一下,而且我们要维护虚儿子的sum和总共的sum,很烦啊!

for(y=0;x;x=f[y=x]){
			splay(x);
			S=s[x]-s[lc];//算原来子树a总和，注意减s[lc]
			ans-=tp[x]<2?(S-(tp[x]?a[x]:s[rc]))<<1:S-1;
			S+=w;s[x]+=w;(y?si:a)[x]+=w;
			if(s[y]<<1>S)si[x]+=s[rc],si[x]-=s[rc=y];//虚实切换
			if(s[rc]<<1>S)   tp[x]=0,ans+=(S-s[rc])<<1;//子树过大
			else{
				if(rc)si[x]+=s[rc],rc=0;//没有子树过大，一定变虚
				if(a[x]<<1>S)tp[x]=1,ans+=(S-a[x])<<1;//自己过大
				else         tp[x]=2,ans+=S-1,rc=0;//都不是很大
			}
		}

夏晓光(loveJY)的博客

碧翠丝的动态树