FlashHu&oyiya的LCT题单

一道一道来。 ## $Chain$ ### $[SHOI2014]$三叉神经树（half half） 这题为啥用$LCT$啊根本看不懂啊$orz$ 首先我们可以发现，如果定义每个点的权值是它儿子1的个数，每次修改实质上就是从这个叶子开始把自它向上权值为$1/2$的一条链变为$2/1$。 那么我们直接树剖套上线段树，每次在线段树上二分，如果全部都是$1/2$就直接修改，否则继续递归。如果修改到根就输出新答案。 注意最后一个点的权值是一定要修改的（比如一坨1改成2，最后面可能有个2要改成3，0要改成1，但对之后深度更小的点已经没有影响了） 这样复杂度是$O(m\log^2 n)$的，难道$SHOI$对这个算法只给了$30pts$？但$4s$能过的啊。 后面想了想，对于$LCT$的算法，应该也是维护一个整条的链的答案吧。但我太菜了看不懂。 ### $[luoguP3613]$睡觉困难综合征（half half） $lxl$好强啊。 一眼秒了一个$O(nk\log n)$的做法，直接按高到低位贪心就可以了。这样好像可以把$NOI2014$的那道原题秒掉。 然后$lxl$告诉我过不了$\cdots\cdots$ $n\times k\times \log n\approx 100000\times 64\times 17=108800000$，加上$LCT$的常数，惨痛。 正确的做法应该是把所有位一起考虑。现在还不会，咕咕咕。 ### $[THUWC2017]$在美妙的数学王国中畅游（zero half） 垃圾题。不知道出题人怎么想的出一道数学题出来。 $$e^{x}=\sum_{i=0}^{\infty}\frac{x^i}{i!}$$ $$\sin(x)=\sum_{i=0}^{\infty}(-1)^i\frac{x^{2i+1}}{(2i+1)!}$$ 直接把$a,b$代进去维护链上系数和。维护个前$11-20$项左右就能保证精度了。 顺便，因为是$ax+b$，所以根据$n$次拉格朗日中值定理，可以让$x_0=b$，比较方便算。 ### $[luoguP1501]$Tree II（half full） 通过这题复习一下加乘区间修改的操作。 乘法的时候，$Add,Mul,Sum$都要$\times x$，注意$pushdown$大概是这样： 左右儿子的$Add,Sum$统一遵循先乘再加的原则，因为我们区间乘法的时候已经将$Add,Sum$也都乘了，如果先加再乘会算重； $Mul$标记也要下放。 仔细脑补一下就可以发现这样不会算重贡献，能正确下放每一次的标记。~~实在不行可以看看线段树2~~ 至于$LCT$的链修改怎么搞，$split(x,y)$，直接从$y$上打标记就可以了。 **注意$LCT$上的~~每个节点没有固定的从属关系，并且~~这个点的答案还要算上它自己，因此比起线段树，它还要多维护一个$Val$表示当前点权值。** ### $[bzoj2157]$旅游（full half） 裸题，唯一要注意的是取相反数操作。这个操作会让$Min,Max$交换，$Sum$换个号。 ### $[ZJOI2008]$树的统计（full half） 太裸了$\cdots\cdots$ ### $[loj6041]$事情的相似度（half full） ~~是的，尽管是我自己出的题，但我并没有想出来怎么做，只推到了倒数第二步。太丢人了。~~ 首先可以发现这个后缀就是$SAM$上$LCA$。那么离线操作，将$r$往右推，很显然要往根跑打标记，如果遇上标记可以直接覆盖，并更新原来标记位置$x$的答案为当前这个点的$maxlen$（上面可以继续覆盖但不用更新答案了）。注意可以直接覆盖因为让位置处在后面的答案更新肯定更优秀。 询问直接区间查询答案最大值，这个用个线段树或者反的$BIT$就可以了。往根跑的过程是$access$，直接用$LCT$维护。 ### $[bzoj2555]$Substring（half half） 这个$half$并不是因为我没想出来，而是因为我忘了$SAM\cdots\cdots$ 感觉建完了$SAM$之后直接$O(\vert S\vert)$找到询问串之后，就$\cdots\cdots$忘了$SAM$怎么维护相同串出现次数了。 $\cdots\cdots$等等我都知道维护这个了为啥还要用$LCT$啊？$SAM$本身不就是一个增量构造吗$\cdots\cdots$ 看了看代码原来$\vert right\vert$是把当前到的这个节点在$parent$树上的父亲全部+1啊。哦那直接上$LCT$吧，更新的时候就$access$一下就可以了。 注意这个题强制在线，所以$parent$树形态会改变，必须要用$link,cut$来更新。~~所以这就是$LCT$维护$parent$树吧~~ 注意这个题的改的边永远是根到路径上的，所以不用$makeroot$，改一下$link,cut$。 ## $EBCC$ ### $[AHOI2005]$航线规划（zero half） 我怎么傻逼题真的不会做了啊？？？？ 根本没有想到树剖这个算法啊。 考虑一条非树边，这条边会使它所属的环的所有边权值归零。修改一条非树边又会将权值变回来。直接用没被删除的边建树就可以了。然后直接用树剖维护。$O(m\log^2 n)$。 或者也可以直接用$LCT\ O(m\log n)$维护边双。这个在另外一篇博客里。 ### $[bzoj4998]$星球联盟（full half） 这题不是裸题吗$\cdots\cdots$ ### $[bzoj2959]$长跑（full half） 这题不还是裸题吗$\cdots\cdots$ ## $MST$ 注意边权要变成虚点+点权。 ### $[WC2006]$水管局长（half half） 因为是最小瓶颈路，直接维护$MST$就可以了。~~我怎么想不出维护MST的方法啊~~ ### $[uoj274]$温暖会指引我们前行（half half） 极其晦涩难懂的题面$\cdots\cdots$ 话说为什么直接最大生成树就能满足条件啊$qwq$ ### $[luoguP4234]$最小差值生成树（half half） 日常想不出傻逼题(1/1) 一开始想了一种如果能使答案变小就贪心断边的做法，$5min$发现是错的。 看了$FlashHu$的题解才发现这不是魔法森林么$\cdots\cdots$ 直接排序后遇到环就去环内掉最小边大概就可以了。 ### $[NOI2014]$魔法森林（full half） 没错，我先做的前面那道题。 曾经觉得特别神仙的这道题现在也可以秒了啊。可惜这并没有什么用。 一开始我是这么想的：考虑先把$a_i$从小到大排序，每次加边的$a_i$肯定是$a$的答案。记一下链上$\max(b_i)$，然后如果遇到了环，$a_i$的增量比去掉那条边后$b_i$的减量要更小，那么直接替换就可以了。因为$a_i$的答案之后肯定不断增加，所以这样的贪心一定是正确的。如果是这样的话，那么还要维护一个次大值。 但我没有想到网友们的做法非常优秀，首先如果新边的$b_i$小于原来最大边的$b_i$就直接替换，那如果出现上面那情况怎么办？直接在每一次换边的时候存一个答案就可以了。首先无论如何之后的每次换边$a_i$一定会更新，然后不管怎么样你至少使$b_i$变得更优了，虽然有可能让答案变劣，但反正你都记下了每次答案。 ### $[bzoj3514]$Codechef MARCH14 GERALD07加强版（zero half） $Rudy$的$NOIp$模拟题有一个套路：一个环里的每条边都记一下这个环的最小编号，如果当前给定的某些边没有最小编号，那就不会成环。~~因为具体的题目描述我忘记了，所以只记得大概长这个样子~~ 想必这个性质被我丢到了记忆的深处。~~也就是说我变菜了~~ 有了这个性质，我们把每条边的这个东西$las$搞出来（如果不成环$las=0$），并把这条最小边弹出去。这样就可以用$LCT$维护最小边了。 考虑答案是什么，就是$n-\sum_{e=l}^r[las[e]<l]$。 考虑一条$las[e]<l$的边，这一定保证了这条边删掉之后会多出一个连通块，那么有了这条边答案就会减1；而如果$las[e]>=l$，意味着无论这条边有没有连通块个数都不会变，所以这条边就不用减。 那么强制在线查$\sum_{e=l}^r[las[e]<l]$可以用个主席树，离线应该可以直接用$BIT$吧。 虽然还有点意思，但我想不出应该是有点问题了，可能得暂停一下做做$ARC$。 ### $[luoguP4319]$变化的道路（zero half） 看错题了$\cdots\cdots$但我连线段树分治的基本思想都要忘了，这是暴露出的一个很重要的问题。 由于有删边，套上线段树分治维护$MST$即可。 ### $[HNOI2010]$城市建设（full half） 比上题有一点简化的就是只修改了权值，那么实际上就是让这条边划分成两个存在区间。记存在区间的时候用个哈希表之类的记一下就可以了。 ## $Subtree$ ### $[BJOI2014]$大融合（full half） 维护的东西显然就是两边子树的乘积。这个东西很好维护，查的时候$split(x,y)$，那么$ans=siz[y]\times(siz[x]-siz[y])$。 ### $[bzoj3510]$首都（full half） 猜了一个结论：两棵树连起来的新重心一定在两个原重心的路径上。~~居然猜对了~~ 有了这个结论就很简单了：每条链维护重心和它离所有点的距离和、子树大小。$link$之后对两个重心$x,y\ makeroot(x),access(y)$，边$access$边处理这些信息，重心就出来了。记得把所有重心异或和记录一下，修改也很方便。 $UPD:$为什么网友们除了两个$log$的启发式合并就是路径上二分啊？？？直接$access$有错吗$qwq$ $UPDD:$我知道了，必须要二分，因为$access$统计的路径信息不完全。要在$access$之后的$splay$上二分，找到那个每个结点统计的在树上的实际子树和与$n-$这个东西差最小的那个儿子就可以了。那这样的话感觉换根不太方便，可以考虑写启发式合并的做法。 或许是我没写姿势水平不太高。 ### $[spoj2939]QTREE\ 5$（zero half） ~~网友：这题不是点分治裸题吗？~~ ~~我：？？？~~ 不会做不会做。~~我可溜了。~~ 很妙啊。 尽管是查一整棵树，但我们可以直接维护子树信息，然后查询就$access,splay$一下。 我们维护每个点的子树内深度最浅白点的深度$near$，以及$\min(near[u]-dep[u])$。 考虑一个点$u$的答案可能是什么，就是$\min(near[u],dep[u]+\sum_{anc_u}near[anc]-dep[anc])$。你可能会考虑到一种情况，就是$u$的一个祖先$anc$的下面的点的子树里有一个白点是最优答案，那时候这个式子就是错的，因为$u$没必要到$anc$。但你稍微考虑一下就会发现那个点是归$anc\to u$上的某个祖先管辖，所以那个答案会在下面算。 为了找到连续的一段颜色，需要维护链上黑/白点个数，然后在$Splay$上二分，然后打上差分标记。 网友们还有高妙的维护左右最大值的$LCT$/边分治+堆做法。 ### $[spoj16549]QTREE\ 6$（zero half） 我们依旧可以考虑一种暴力的做法，就是直接维护这个点颜色为$0/1$时子树内极大连通块大小。这样换颜色也只会对往祖先的一条同色链产生影响，直接将它们的值改一下，维护这个点两种颜色的情况是为了方便换颜色的时候的更新答案。这种方法与上面那种类似。 或者还有一种更妙的方法，如果你考虑过一种暴力，一个点换颜色将它在原树上原来连的边都$cut$，不连的边都$link$，复杂度在菊花下是$O(n^2)$的。 但我们可以每个点的颜色映射到这个点到它父亲的边上（这貌似已经是个常见的套路了），然后按照黑白颜色弄两棵$LCT(Forest)$，那么当前结点的极大连通块大小就是它所在的这棵树把根连向儿子的那些边删掉得到的那个连通块大小。 这样每次修改直接把父边断掉，连到另一棵树上就可以了。 至于答案，$findroot$的时候已经$access$了这个点，那最后$splay(root)$，输出重儿子子树大小就可以了。 注意$1$号结点也需要一个父边来保证答案正确性。 ### $[spoj16580]QTREE\ 7$（zero half） $QTREE\ 6$的加强版。但需要维护**虚**子树最大值，并资瓷删除。 于是得套个$multiset$。 ### $[uoj207]$共价大爷游长沙（full half） 因为对这个题目有点印象，所以知道它是哈希之后很快就想出来了。 对每条路径的端点给一个随机值。考虑如果一条边被所有路径经过，那么这条边两个端点两边的子树和一定是一样的，统计一下就可以了。 网友们有更方便的方法，直接求任意一边的异或值，如果被所有路径经过，这一定会与我们随机的所有权值异或和相等。这样似乎可以少讨论一点。~~总感觉我每次想题都会想复杂。~~ ### $[SDOI2011]$染色（full half） 因为跟树剖一模一样所以直接跳了。但是$splay$森林的思想很不错，可以用来加深对$LCT$的理解。 ### $[cogs2701]$动态树（full half） 裸题。第二问就是求$access$后虚子树大小+1。 ### $[loj6038]$远行（zero half） 我之前想的做法很$naive$，直接维护每个点子树到这个点的最长链。这个东西很显然可以直接$pushup$，每次查询直接$makeroot$就可以了。 后来发现不能$makeroot$，于是想通过$access$的套路找答案。 发现此题是维护最大值，直接求$\max$会有答案错误的点，遂凉凉。 正解用到了直径的性质，就是树合并之后的直径端点是四个端点之一。 其实可以直接用并查集维护直径端点，用启发式合并即可。求动态距离可以用倍增，每次暴力重构倍增数组，复杂度应该是$O(n\log^2 n)$的。~~但我觉得跑得比$LCT$快~~ 追求一个$\log$就用$LCT$维护树上距离吧。 ## $Connected\ Blocks$ ### $[ZJOI2012]$网络（full half） 题目这个性质显然直接就是询问一条链。对每种颜色分别建图，每次询问可以直接暴力枚举。 ### $[SDOI2017]$树点涂色（full half） ~~很抱歉，我又没有想出LCT解法。~~ 通过观察可以发现一个性质：对于一条向根的链，下面的颜色肯定比上面的老，而且不会出现一种颜色在两个不连续的地方出现。 那么我们需要记录的就是这个点是不是关键点（即这种颜色的终结点），每次1操作就是把这个点到根的关键点全部抹掉，然后修改子树的答案。修改的时候就让子树的答案减去这个点到根链上的关键点个数再加1。对于3操作可以直接查询子树答案最大值。 2操作也很显然，一条链可以拆分成$x\to lca,y\to lca$，然后两条链的颜色不可能有重叠部分，直接查就可以了。 ~~所以SDOI出这种码量巨大的题意义究竟何在啊？要么写难写的树剖，要么写难调的LCT，或许有R2还有D2一共12道题是真的可以单独拿一道题来测试选手的代码能力吧。~~ ### $[WC2005]$Dface双面棋盘（half half） 总算搞懂怎么维护连通块了$\cdots\cdots$之前一直都是半吊子水准。 然后就是裸题了。 这题比较恶心，每次有四条边还得把边变成点$\cdots\cdots$ 貌似还有$CDQ/Seg\_Tree+DSU$的奇妙~~暴力~~做法。 ## $Special$ ### $[ZJOI2016]$大森林（half half） ~~ZJOI2016的大森林和小星星我都没想出来，要退役了啊~~ 我最深也就想到了这玩意儿相邻的树是相似的，而且一定要建个虚树出来在上面求距离，然后就完全想不到了。 看了一下午题解好像明白了一点，大致是把生长节点的虚点拉出来直接扫一遍区间吧。目前还没看懂，咕咕咕一下。 ### $[ZJOI2018]$历史（half half） 可以发现链非常好做，直接从下到上崛起。可以发现这样的一次轮流崛起后，情况会再次变成由这次崛起的所有城市构成的情况。但这样是$O(nm)$的。 考虑用一个线段树维护每个点的答案，修改就把$dfn$大于它的点的答案改一下，求个区间和就可以了。 我想的做树的策略过于复杂细节很多还是暴力无法优化，估计正解的性质应该非常优秀。 $UPD:$果然，链做法和正解半点关系都没有。 **** 首先，我们发现每个点的贡献是独立的，它产生贡献仅在于它自己崛起，或者它的子树崛起，且如果上一次崛起的点与这一次都不是它自己，那么它们并不属于同一个子树，因为如果属于同一个子树，战争肯定发生在下面的点上。当然，这两个点也不能同时为自己。 **** 考虑这个点能产生的贡献是多少。设每个点$u$子树内崛起次数总和为$siz[u]$。 **** 假如存在$u$的儿子$x$满足$2siz[x]>siz[u]$，也就意味着这个儿子的子树大小比其它（包括父亲的次数）加起来还要多，那么即使是$x,oth,x,oth\cdots$这样崛起，$x$的次数还是用不完。因此这种情况下，最大的崛起次数就是$2(siz[u]-siz[x])$。这种情况下第一次崛起是可以忽略的，因为实际上我们的过程是$x,oth\cdots,x,oth,x$，第一个$x$虽然无效，但是后面的$oth,x\cdots$过程才是产生答案的过程。 **** 如果不是这样的话，那意味着$x,oth,\cdots$这种崛起方式肯定能把$x$弄完。如果其它的崛起次数多了怎么办？就可以类似$x,oth1,oth2$这种形式插进去，可以发现一定能插完。那么这种情况的答案就是$siz[u]-1$，因为第一次崛起不算。 **** 于是，在以上的情况下我们就能够在$O(n)$的时间内通过$dfs$得到结果。现在来考虑动态修改的过程。 首先我们可以有一个链剖分的定义，那就是如果$u$的儿子$x$满足$2siz[x]>siz[u]$，那么就让$u\to x$连一条重边，否则连轻边。显然每个点最多有一个重儿子，每个点祖先的轻边个数最多是$O(\log)$的，这些比较显然。可以发现如果有重边，它对父亲的贡献就是$2(siz[u]-siz[x])$。 首先每个点的修改只会影响到这个点的祖先。注意到题目每次只会加上而不会减去一个值，那么也就意味着原来到根路径上的重链不会改变，而且对重边的答案也没有影响（差不变），因此只需要考虑轻边变成重边的问题。 因此用$LCT$维护这棵树，每次$access$就考虑当前轻边可否变成重边、当前遍历到的点在其它地方的重儿子要不要扔掉就可以了。更新的时候打上链加标记。 正确性是这样的：因为每次$access$都是一个一个重链的跳，那么你能够跳到的$x$一定是重链的链顶，而且$x\to fa[x]$是一条轻边，你只要考虑这条边就可以了。 ------------ 学到了一种打到根链加标记的新套路：$access$的时候$splay(x)$之后，$son[x][0]$那边就是这条重链原来的部分，给它打个标记之后这条链就加完了。 ------------ 网上的题解大都转成了$LCT$那个模，感觉很没有意义。 ### $[LNOI2014]$LCA（zero half） 一开始想到了是链上每个点子树内的询问点个数，结果并没有想出来。瞄了一眼hyj的转模。 瞄完之后没有一点想法。滚粗感++ 然后看完题解发现自己真智障$\cdots\cdots$怎么连离线都不知道了$\cdots\cdots$ 首先有一个转模，就是让$[l,r]$每个点到根路径上加1，答案就是$z$到点的权值和。 有了这个转模问题其实就很简单了，直接离线询问，然后一个一个点进行链加，把每个询问拆成两个，但对应的编号一样。然后就可以差分查答案了。 赶紧回忆一下离线技巧。 ### $[bzoj2759]$一个动态树好题（half half） 没有看到树结构会变，以为能用树剖维护，$GG$。 实际上这个套路做过一次，考虑树上的所有点都可以被$x[root]$表示，加上环的那条边下面那个点又可以被一种新的方式表示，那么这样两个方程联立就可以求出$x[root]$。 注意如果当前结构是树，或者出现$0\equiv 0$这种情况就是多解。