树分治小记

command_block

2020-04-09 14:20:10

Personal

最近你可能在本Blog看到许多这样的小记,这完全属于省选之前的游击战术,内容不保证严谨,也不保证大多数人能看懂。

如果省选过后有时间我会来仔细更新并且把这些文字去掉的。

可能你会发现没有代码,这是因为我懒得贴,而不是在口胡或者咕咕咕,等我有空了会回来补的。

少数题目可能没有评测之处,这我也无能为力。

内容比较杂,大概有:

有些(带记录标记的)链接会直接拉到博客中的其他文章(更丰富的)讲解,并不是一句话题解,请留意。

点分治

用于解决一类树上路径问题。

核心思想 : 每次钦定一个点,只统计经过该点的路径。然后各个子树之间便不再有贡献,可以分治。

在树上,只需要选取重心作为分治中心,则可以保证各个子任务的规模都不超过原问题的一半。分治的深度是严格O(\log_2n)的。

然后,就变成了只处理过根的路径。一般来讲考虑“深度”,分上下讨论就可以了。

以当前分治中心为根,经过根的路径的长度可以转化为两个端点的深度。

我们要拼合出恰好为k的路径,由于k较小,可以直接开桶维护。

主要的难点在于,路径不能自交,也就是说,两个端点必须来自不同子树。

解决的方法类似树形DP,先查询完某棵子树,再将其加入桶中(或其他数据结构)。这样就能保证只有来自不同子树的无序对才有贡献。

可以每次枚举修改来清空桶。

子问题大小总和是O(n\log n)的,总复杂度与之相同。

提交记录

观察到k仍然很小,使用树状数组维护前缀和即可,复杂度是O(n\log^2n)。

选取分治中心之后,令mx[u]为u到根的边权\max。

一条路径(u,v)的贡献即为\max(mx[u],mx[v])。

这里我们略施小计,把有序的路径钦定为在mx值较大的一段贡献。注意答案最后乘个2。

现在要计算总贡献。分“是最大值”和“不是最大值”讨论即可。

对于半截路径mx[u],只需要考虑mx不超过自己的路径。

贡献为 : 不超过mx[u]的路径数\times mx[u]。别漏了分治中心本身。

这里还需要受到边的条数的限制,就变成了一个二维偏序问题。

但二维偏序是静态的,我们无法像前文那样依次加入各个子树。

注意到,求和类问题可以支持减去贡献,我们在每个子树内单独跑一次把贡献减去即可。

复杂度O(n\log^2n)。评测记录

相信做过上一题之后能看出来是个裸的点分治+二维偏序。复杂度O(n\log^2n)。

评测记录

从重心计算若干个向上和向下的括号路径。

对于向上的路径,括号对消之后一定得到若干个 ( 。若遇见无法对消的 ) ,则不合法。

对于向下的路径,括号对消之后一定得到若干个 ) 。若遇见无法对消的 ( ,则不合法。

具体而言需要维护一个栈。

对于向上的路径,后来 ( 的可以消去前面的 )。

对于向下的路径,后来 ) 的可以消去前面的 (。

栈在要记录是否曾经对消,便于回退。

只有消完之后括号数量相同的半路径才能够匹配。

注意,题目中求的是括号序列的“最大深度”所以还要维护这个东西。

抽象成+1-1前缀和就容易维护了,注意还要考虑栈中未对消的括号。

由于路径长度是O(分治块大小)的,开个桶维护一下就好了。

这是取\max,贡献不可减,桶是支持动态加入的,那就沿用依次加入各个子树的方法。

我们可以把向上的路径加入桶,而用向下的路径来查询。不过这样就变成了有序对,需要正反各做一次。

评测记录

需要保存每条路径端点的颜色,如果两条路径端点颜色相同,则会减去一次贡献(可能是负数)。

有路径长度的限制,仍然考虑线段树维护。

现在我们要同时考虑端点颜色和子树编号两个限制,似乎有点麻烦。但是能够发现,端点颜色是取决于子树编号的。

我们把所有路径按照端点颜色为序,一次加入一个颜色,这就计算完毕了不同颜色之间的贡献,而且不会在同一子树内重复。

然后,我们对于每一种颜色,再分别按照子树编号依次加入即可,此时需要减去一次贡献。

注意清空线段树,这里并不需要标记。还要注意单独考虑从根向下的路径。

这题比较卡常数,O(n\log^2 n)似乎并不是正解,但随手加几个最优性剪枝就飞过去了。

评测记录

仍然是分上下讨论。我们钦定向上的路径包含根。

记录所有向上能到达根的路径,最多余下多少油。

我们一边向下dfs,一边维护油量的“最深坑”,也就是负得多惨。

我们要保证一路的油量都大于等于0,开始时的油量就不低于“最深坑”。

所有向下的路径,抵达终点需要在初始时额外支付多少油。计算方法类似。

然后排序再双指针扫一下,由于是求和问题,可以采用容斥的办法。

评测记录

按重心移动

题意 : 给出若干个点对,要求选定一个点c。

点对(u,v)的花费定义为dis(c,u)+dis(c,v),问如何选定c使得所有点对花费的最大值最小。

考虑先随意使某个点为c,求出各个点对的花费,此时为两个点深度的和。

找出花费最大的点对(们)。

如果c在点对间的简单路径上,即点对在不同子树内,答案不可能变小。

又或者多个最大值分布在不同的子树内,答案同样不能变小。

反之,c只有向着最大点对所在的子树移动,才可能让答案变小。

于是,我们排除了其余各个子树。这相当于只递归一边的点分治。

我们每次找出点对需要遍历整棵树,是O(n)的,只需要O(\log n)(分治树深度)次,总复杂度是O(n\log n)的。

注意,由于是跳跃移动,答案可能反而变劣,需要不断取\min。

还有grt中覆盖vis的情况需要先判掉return。

评测记录

首先考虑如果给出一个点集,我们要怎么安排顺序使得答案最大。

能够发现是找到重心,答案就是各个点到重心距离的两倍。

考虑构造 : 在重心的不同子树之间穿插,使得路径总是经过重心。

由于最大子树不超过k/2(即便是散点集,边加了权,仍然有这个结论),一定能造出来。

如果任何一个路径不经过重心,答案都会变小。

然后考虑利用重心的性质。先猜测一个重心,在各个子树中贪心地选取深度前k大的点。

如果我们猜中了最优答案,没有一个子树选取的点数会超过k/2。

我们先要证明,这是答案最优的充要条件。结论 : 重心到点集距离和最小。

假设我们已经有一个符合如上要求的重心v,但另有最优解u在旁等候。我们可以令u中选定的点集连接到v上,这会使得距离和增大(因为v不是他们的重心),然而这和v是局部最优解矛盾。

如果很不幸,某个子树选取的点数超过了k/2,我们很有理由怀疑,更优的重心在其所指的方向。

我们可以将此时的点尽量穿插配对,然而在最大的子树内,仍然有一些点无法和外面配对。

如果我们让重心远离它们,这样它们会“变深”,身后的少数点会“变浅”。这样,反而会助长最大的子树的扩张。

所以,为了让没有一个子树选取的点数会超过k/2,我们必须向着最大的子树进发。

按照套路,每次向着子区域的重心移动,复杂度是O(n\log^2n)的。

注意,当k为奇数的时候,可能出现两个子树选满(k-1)/2个点,而最后一个点不知道选在哪边的情况,似乎是不太可做的。

边分治

点分治中,我们每次统计“只统计经过中心的路径”

边分治中,我们每次统计“只统计经过某条边的路径”。

这条边的选取也很讲究,需要选择两侧联通块尽量均匀的那一条。方法类似。

直接上的话,复杂度是不对的,给一个菊花图就卡掉了。

我们可以添加一些虚边虚点,使得整个图的度数不超过3,称之为三度化。这样子就能切得比较均匀了。

注意,这些新加入的东西不能影响答案,一般边权为0。如图:

由于三度化和虚边虚点处理,边分治一般要比点分治难写。

边分治有什么好处呢?每次分治的时候,子问题只会被切成两半,这会带来一些好的性质。

建议先使用边分治写点分治的题来熟练,如 P4149。

先不写三度化体验一把TLE的快感。

边分治时,找到分治边后,需要将其删除,此时用邻接链表较为方便。

评测记录 ,常数并不大。

先以任意一个点为根,预处理出从根到每个点的异或和w[u]。

由异或的自反性,两个端点的w值xor起来就是路径异或和。

考虑点分治,现在A权值和被转化成了两个深度和,这一维的限制变成了偏序。

我们发现,我们只能建立静态的可持久化01Trie来应付查询,但是这里的贡献不可减,无法容斥。

所以我们转而采用边分治。在边分治中,只有两个子树。

我们只需要在其中一个建立静态结构,然后从另一个出发查询即可。

事实上,点分治如每次合并(直接重建)两个最小的静态结构,并且处理之间的询问,复杂度仍然是正确的。边分治在比较经典的题目中没有多大优势。

链分治

我对这东西没啥很好的理解,暂且随便一讲。

对于路径统计问题,还有另一种思路 : 钦定一个根变为有根树,并且枚举LCA。

一般来讲,我们会按照dfs的顺序来逐次访问各个节点,这样,我们就能够挑选某个儿子来继承信息。这或许能够改善复杂度。

先将这棵树按照某种规则进行链剖分,即为每个点选择一个“重儿子”,优先dfs并保留信息,并将其他轻儿子的信息加入。

在加入信息之前,我们计算新信息与旧信息之间的贡献,不难发现他们代表的路径的LCA一定是当前点。

能够注意到,我们必须维护支持动态加入的数据结构(或者二进制分组?)。

其实可以看做一次删去一条链,dfs的行为也是如此。

某些时候,这类方法也不止于路径统计问题。

我们可以用平衡树维护深度和边数,区间取\min即可。

树上启发式合并维护,复杂度是O(n\log^2n)或O(n\log n),本质上是在重链剖分。

其实直接写线段树合并会达到货真价实的O(n\log n),但是似乎脱离了我们链分治的分析。

注意到允许离线,我们用栈+dfs就能够轻松求出某个点的k级祖先。

现在问题就变成了 : 某个点子树内,距离该点为d的点的个数。

我们维护f[u][d]表示点u子树内,距离该点为d的点的个数。

不难发现,状态量和子树最大深度相关,我们采用长链剖分维护这个dp。

轻儿子的继承直接加法,是O(n)的。

重儿子的继承是难点,需要巧妙的分配空间。善用指针。

如果v是u的重儿子,把f[u][1...len[u]]分配给f[v][0...len[v]],这样直接传上来就符合定义。

其他的题目可能没这么幸运,可能要对这些信息批量操作。

评测记录

考虑朴素的树上启发式合并,用数组维护每个颜色出现的次数,以及出现\geq i次的有几种颜色,不难做到O(1)增量。

但是数组需要的空间较大,且不和时间(子树大小)有关,我们不能为一路上的每一个重儿子都开一个数组。

考虑如何只采用一个全局数组来维护。

先计算轻儿子内部的答案,并将其对全局数组的影响清除。(只是完全清除而已,不一定需要贡献可减)

然后计算重儿子的答案,并将其信息保留并且继承。

然后再次计算轻儿子的影响,和(之间的)贡献。

这种算法被一些人称之为 dsu on tree。

复杂度仍然是轻儿子子树大小的和,O(n\log n)

提交记录

可以对于每条边分别考虑贡献。

发现跨越某条边的区间数不容易计算,但是不跨越的区间数较为容易。我们只需要分别考虑子树内和子树外。

我们其实就是要维护一堆位置包含了多少个区间。

考虑dsu on tree子树内在加入,子树外在删除。

对于子树内的,我们可以采用并查集维护。对于子树外的,可以用类似ODT的办法。

重儿子继承比较简单。但是影响清除只需要把并查集指针恢复原样,ODT初始化为一整个大区间即可。

复杂度是O(n\log^2n)。

[提交记录] ()

点/边分树

在这一节中,我们更多地用它们来建模。

这相当于点分树计数。我们需要设计一个树形DP,但是树上的某边对点分树的影响比较难以分析。

我们考虑断开一条边u,v之后,如何拆分点分树。

设边一侧的点为白点,另一侧为黑点。对于每个点向上找到大点分树上的第一个同色祖先为父亲。

性质 : 任意两点的点分树上LCA,一定在原树中两点的简单路径上。

根据联通块的性质,可以推导出 : 如果两个点同色,则原树路径上的点都同色。

这也就是说,点分树上两个点同色,则它们的LCA与其同色。这就能证明两种颜色的点都各自连成一棵树(而非森林)。

反过来考虑,如果我们连接了一条边(u,v),如何合并点分树。也就是说考虑什么样的大点分树能够拆成这两个小的。

容易得到 u,v 合并后必然在同一条直上直下的链上,除此之外的约束只有父子关系。

一个结论是 : 我们只需要考虑把 u 到点分树根的路径和 v 到根的路径按任意顺序归并。

为啥不能动旁边挂着的子树呢? 其实我们可以证明分裂时,u到点分树根的路径上挂的树都是纯色的。

考虑反证,如果颜色不纯,则会与其他的异色点呼应产生LCA,而这个LCA正是u到点分树根的路径上的点,矛盾。

经过上述一阵毒瘤的推导,我们现在只需要关注子树的根节点在点分树中的深度。

设f[u][i]为点u的子树建立点分树,u本身深度为i的方案数。

在把u与儿子v贡献合并的时候有:

f'[u][i]=\sum\limits_{j=1}^i\sum\limits_{k=i-j}^{siz[v]}f[u][j]*f[v][k]*\dbinom{i-1}{j-1}

组合数这里减一是因为钦定了第i位。注意,归并方案数和k无关。

对f[v][k]做一个后缀和,再加上子树大小剪枝,就可以做到O(n^2)了。

动态 · 树分治

特意把标题加个点,不要搞错了。

众所周知,猫树是序列上的点/边分树,那么某些东西猫树能(动态)做,点分治能做,就说不定能上点分树。下面可能点分和边分傻傻分不清。

点分树的祖先节点相当于把从 u 出发的所有目的地划分成了O(\log n)个联通快,而且有必经点,所以方便处理。

动态链分治不知道该怎么更通俗地描述,因为这东西恐怕只存于树中。大概就是考虑路径所经过的最高重链,以及最高处是轻链的情况。

没有修改,但是强制在线。应该是难度最低的点/边分树套数据结构了。

图已经三度化,考虑边分治。从u开始在边分树上向上跳,会经过O(\log n)条关建边。

在每条关建边处,查询对面年龄范围内的点的距离和,注意要加上点数\times自己到关键边的距离。

这可以排序+前缀和维护,需要二分来查找界限。

到关建边的距离(深度)可以分层来存储。善用指针代替vector分配你的内存。

复杂度为O((n+q)\log^2n),空间复杂度是O(n\log n)。

评测记录

注意到答案是求和的形式,可以容斥成对前缀的询问。

这就可以采用可持久化边分树来做,按照年龄依次加入修改得到前缀的状态即可。

具体来讲,需要维护已经存在的深度和,以及个数和,这只需要O(1)个变量存储就好了。

可持久化的时候,需要把到根的路径path copy,还要记录往哪边走,具体见代码。

复杂度为O((n+q)\log n),似乎比可持久化树剖时空双优,但是仍然打不过。

评测记录

由于带负权,直径的经典结论不再生效。

① 动态点分治

按照点分树深度用O(\log n)个数组存下距离信息。

对每个分治中心,每颗子树维护一个可删堆。

对于各个子树的堆顶再维护一个可删堆,我们每次取出第一和第二即可。(若采用边分治可省去)

对于全局的答案,还要维护一个可删堆。

总复杂度是O(n\log n+m\log^2n),空间是O(n\log n)。

② 动态链分治

我们从被修改的点向上更新,只会经过O(\log n)条重链。

考虑某条重链, d[i]是 i 号点沿轻链下行的最长长度, s[i] 是重链上两点的距离前缀和。

我们要在答案路径经过的最高重链将其捕捉,这相当于维护最大的 [i<j]d[i]-s[i]+d[j]+s[j]。

分别维护 (d[i]-s[i]) 和 (d[j]+s[j]) 的区间最大值,然后pushup时更新跨过中线的贡献即可。

向上更新的 d 可以取用本条重链 (d[j]+s[j]) 的最大值。

只有对 d 的单点更新,可以(每条重链分别)使用线段树维护。全局的路径再使用一个堆维护。

注意,某个点的 d 可能有多种来源(多个轻儿子),所以不能直接赋值,需要用可删堆维护。

我们还需要考虑路径的最高点不是重链而是轻链的情况,这等价于在维护 d 的堆里面取出最大值和次大值。

复杂度是O(n\log n+m\log^2n),常数较小。评测记录

现在变成指一个点询问最近的白点,而不是整体问题。

考虑这个点所在的重链,对应着前缀查询 d[i]-i 的最大值,或者后缀查询 d[i]+i 的最大值。

注意,可能与本点的(其他)轻链组成答案,同样在可删堆里面搞搞。

维护 d 是类似的。 提交记录

点分治当然也能做,由于绕路一定不优,可以不处理重复的贡献,代码较短。提交记录

在没学点分树之前一直以为这东西不可做。

这个模板题并不是最简单的点分树,如果我还能找到更简单的就会更新。

评测记录

链分治并不太能做,因为轻链只能传递少量信息(适合传统的单路径统计),而这个题需要以深度为序的较多信息。

用于解决树链操作这一经典问题。

显然是可以直接树剖做的,但是复杂度为O(n\log^2n)。

LCT的复杂度是O(n\log n),但是常数过大,实际效率并不会更优秀。

现在就要祭出上古魔法 : “全局平衡二叉树”。(可见《QTREE解法的一些研究》,2007)

树剖无疑比LCT更加轻便(指思想和分析)。轻重链的选择十分自然,每条重链都用完美平衡的静态结构来维护(虽然更多人的做法是写一个大结构)。可惜的是,复杂度是O(n\log^2n)。

究竟是什么设计,让Splay胜过完美平衡的静态结构呢?

我们考虑学着LCT把轻边拎着的重链的维护结构,挂在真正的父亲上,而且认父不认子。

我们引用一张古老论文里的例图,顺便一睹全局平衡二叉树的真容:

(“二叉树”这个称呼似乎不那么精确,应该称“二叉树森林”或者“多叉树”,取决于算不算轻边)

若要链操作,而在一条重链上区间操作,从全局树上看,下一条待命的重链正好挂在上一次结束的点上。

我们惊奇的发现,这棵全局树的深度,正对应链操作的复杂度!

而树剖的结构只是局部平衡,连上轻边之后可能导致深度增加到O(\log^2n)。

(不过倘若不刻意卡,常数会很小。而另一个好处是可以询问和操作子树。)

下一步是试图造出一棵深度为O(\log n)的全局树。

若要做到这一点,我们必须认识到 : 单条重链结构的点不止代表了自己,还代表着挂着的一大堆虚子树。

我们可以设s_i为重链上第i个点本身以及挂着的一堆东西的总大小。这些玩意必须按顺序组成一棵排序树。

我们将其排成一排,找到“重心”,也就是把左右两边分得尽量平均。然后将重心作为根,两侧递归建树。

我个人更习惯Leafy的结构,因为更便于拆分区间和可持久化。如果需要构建这样的结构,这里的“重心”就要变为类似边分治的“关建边”。

我们来证明复杂度 :

加权找重心是危险的,因为大块头往往会令人失算。

先不考虑重心及其连带着的部分,不难证明,剩下的两部分都总是小于(\sum s_i)/2的。

而重链的性质很好,被我们拎出来的重心挂着的轻儿子总和,同样不会超过整个子问题规模的一半。

这就证明了全局树的深度是O(\log n)的。我们构造时的复杂度不超过其每个点的子树大小和,为O(n\log n)。

这棵树是静态结构,常数较小,复杂度货真价实,也并不难实现。

实际上,大多数的操作都可以跳父亲无递归实现,这和点分树有点类似。

可能你发现了,这些操作都是到根的。实际上,不到根的路径操作(区间而非前缀)如噩梦般难写,如果遇到了还是弃疗写树剖吧……

如果将同一个点上挂着的轻儿子,同样使用加权二叉树维护,似乎就能够做到子树操作(静态Top tree?)。

真正的毒瘤 到 来 了 。

先不考虑挂叶子,进行普通点分治。

每次选定分治中心之后,答案是 dep[u]+dep[v]\leq r[u]+r[v] 的点对数目。

可以变成 dep[u]-r[u]\leq r[v]-dep[v]。使用平衡树维护。

挂叶子的时候,我们可以暂且在点分树中,先将其挂在父亲的下面。

沿着点分树一路向上更新,会有 O(h) 个计算路径长度(需要倍增),以及平衡树插入操作。

然后需要查询贡献。在每个分治中心处,需要查询其他子树的贡献。

这可以维护一个大平衡树,再给每颗子树维护一个小平衡树,查询两次减去即可。

但是,随着叶子越挂越多,点分树的深度 h 也会变深,将会导致复杂度退化。

一个憨逼的想法是 : 模仿替罪羊树,重构不平衡的局部点分树。

重构的时候其实就是局部点分治,由于需要 sort 建立平衡树,复杂度是两个 \log 的。

可以考虑对较大的数组基数排序。具体地讲,在 O(n\log n) 和 O(n\log_nS) 之间权衡,这样可以把排序的 \log n 摊平成 \sqrt{\log S} ,而且不会增大常数。

传统替罪羊的重构比修改低一个 \log ,此时 \alpha=0.75 才比较快。

本题中而重构复杂度较大,则需要把 \alpha 调大一点 (如 \alpha=0.8 )。

仔细分析,将替罪羊在最差情况下理解成类 a 进制分组,则重构的复杂度是 lowbit 求和,为 O(n\log_a n) ,修改的复杂度为 O(an\log_an)。

本题中,这样所能得到的最优复杂度为 O(n\log^2n\frac{\sqrt{\log S}}{\log\log n}) (毒瘤,反正比 O(n\log^3n) 要快)

平衡树一定要比较快,不然可能被卡常数。需要写个内存垃圾桶来回收平衡树节点。

局部点分治的时候,可以先跳父亲来封边界。

注意某个联通快块重构之后,父亲还是得更新。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define INF 1000000000
#define MaxN 100500
using namespace std;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
struct BST_Node
{int l,r,x,c;}a[MaxN*66];
int rub[MaxN*66],rut,tn2;
int cre(){
  if (!rut)return ++tn2;
  int pos=rub[rut--];
  a[pos].l=a[pos].r=0;
  return pos;
}
int sx[MaxN],st2[255],tot2;
struct BST
{
  #define st st2
  #define tot tot2
  int rt;
  BST(){a[rt=cre()].x=INF;a[rt].c=1;}
  inline void up(int u){
    a[u].x=a[a[u].r].x;
    a[u].c=a[a[u].l].c+a[a[u].r].c;
  }
  int find(int x)
  {
    int u=rt;tot=0;
    while(1){
      if (a[u].l==a[u].r)return u;
      st[++tot]=u;
      if (x<=a[a[u].l].x)u=a[u].l;
      else u=a[u].r;
    }
  }
  void del(int u){
    rub[++rut]=u;
    if (a[u].l==a[u].r)return ;
    del(a[u].l);del(a[u].r);
  }
  void clr(){del(rt);rt=0;}
  void pia(int u)
  {
    if (a[u].l==a[u].r){
      sx[++tot]=a[u].x;
      rub[++rut]=u;return ;
    }pia(a[u].l);pia(a[u].r);
    rub[++rut]=u;
  }
  void build(int l,int r,int &u)
  {
    u=cre();
    if (l==r){
      a[u].x=sx[l];a[u].c=1;
      return ;
    }int mid=(l+r)>>1;
    build(l,mid,a[u].l);
    build(mid+1,r,a[u].r);
    up(u);
  }
  #define chk(u) a[u].c*31 < 40*max(a[a[u].l].c,a[a[u].r].c)
  void add(int x)
  {
    int u=find(x),nu=cre(),nv=cre();
    a[nu]=a[u];a[u].r=nu;
    a[a[u].l=nv].x=x;a[nv].c=1;
    up(u);
    int reb=0;
    for (int i=tot;i;i--){
      up(st[i]);
      if (chk(st[i]))reb=st[i];
    }if (reb){
      tot=0;pia(reb);
      build(1,tot,reb);
    }
  }
  int rnk(int x)
  {
    int u=rt,ans=0;
    while(1){
      if (a[u].l==a[u].r)return ans;
      if (x>=a[a[u].l].x)
        {ans+=a[a[u].l].c;u=a[u].r;}
      else u=a[u].l;
    }
  }
  #undef st
  #undef tot
}T[MaxN],T2[MaxN];
vector<int> g[MaxN],l[MaxN],tv[MaxN];
void adl(int f,int t,int len){
  g[f].pb(t);l[f].pb(len);tv[f].pb(0);
  g[t].pb(f);l[t].pb(len);tv[t].pb(0);
}
int st[MaxN],tn,ms[MaxN],siz[MaxN],
    tef,ef,vis[MaxN];
void pfs(int u)
{
  siz[st[++tn]=u]=1;
  vis[u]=ef;ms[u]=0;
  for (int i=0,v;i<g[u].size();i++)
    if (vis[v=g[u][i]]<ef){
      pfs(v);
      siz[u]+=siz[v];
      ms[u]=max(ms[u],siz[v]);
    }
}
int grt(int u)
{
  tn=0;ef++;pfs(u);
  int rt=0;
  for (int i=1;i<=tn;i++){
    ms[st[i]]=max(ms[st[i]],tn-siz[st[i]]);
    if (ms[st[i]]<ms[rt])rt=st[i];
  }return rt;
}
struct PDC_Node
{int f,c,d;}t[MaxN];
int r[MaxN],d[38][MaxN],*td,sd[MaxN],tot;
void gdis(int u)
{
  sd[++tot]=td[u]-r[u];
  vis[u]=ef;
  for (int i=0,v;i<g[u].size();i++)
    if (vis[v=g[u][i]]<ef){
      td[v]=td[u]+l[u][i];
      gdis(v);
    }
}
void qs(int *s,int n)
{
  if (n<=256){sort(s+1,s+n+1);return ;} 
  static int o[260],g[MaxN];
  for (register int i=1;i<=n;++i)s[i]+=INF;
  for (register int i=1;i<=n;++i)++o[(s[i]&255)+1];
  for (register int i=1;i<=255;++i)o[i]+=o[i-1];
  for (register int i=1;i<=n;++i)g[++o[s[i]&255]]=s[i];
  memset(o,0,sizeof(o));
  for (register int i=1;i<=n;++i)++o[((g[i]>>8)&255)+1];
  for (register int i=1;i<=255;++i)o[i]+=o[i-1];
  for (register int i=1;i<=n;++i)s[++o[(g[i]>>8)&255]]=g[i];
  memset(o,0,sizeof(o));
  for (register int i=1;i<=n;++i)++o[((s[i]>>16)&255)+1];
  for (register int i=1;i<=255;++i)o[i]+=o[i-1];
  for (register int i=1;i<=n;++i)g[++o[(s[i]>>16)&255]]=s[i];
  memset(o,0,sizeof(o));
  for (register int i=1;i<=n;++i)++o[(g[i]>>24)+1];
  for (register int i=1;i<=255;++i)o[i]+=o[i-1];
  for (register int i=1;i<=n;++i)s[++o[g[i]>>24]]=g[i];
  memset(o,0,sizeof(o));
  for (register int i=1;i<=n;++i)s[i]-=INF;
}
void build(int u,int dep)
{
  t[u].c=1;
  (td=d[t[u].d=dep])[u]=0;
  vis[u]=tef;tot=0;
  for (int i=0,v,sav,vrt;i<g[u].size();i++)
    if (vis[v=g[u][i]]<tef){
      tv[u][i]=vrt=grt(v);
      sav=tot;
      td[v]=l[u][i];
      ef++;gdis(v);
      T2[vrt].clr();
      for (int j=sav+1;j<=tot;j++)
        sx[j-sav]=sd[j];
      qs(sx,tot-sav);sx[tot-sav+1]=INF;
      T2[vrt].build(1,tot-sav+1,T2[vrt].rt);
    }
  sd[++tot]=-r[u];
  T[u].clr();
  for (int i=1;i<=tot;i++)sx[i]=sd[i];
  qs(sx,tot);sx[tot+1]=INF;
  T[u].build(1,tot+1,T[u].rt);
  for (int i=0,v;i<g[u].size();i++)
    if (vis[v=g[u][i]]<tef){
      t[v=tv[u][i]].f=u;
      build(v,dep+1);
      t[u].c+=t[v].c;
    }
}
int f[MaxN][18],dis[MaxN],dep[MaxN];
int lca(int x,int y)
{
  int k=17;
  if (dep[x]>dep[y])swap(x,y);
  while(k--)
    while(dep[f[y][k]]>=dep[x])
      y=f[y][k];
  if (x==y)return x;
  k=17;
  while(k--)
    while(f[x][k]!=f[y][k])
      {x=f[x][k];y=f[y][k];}
  return f[x][0];
}
int dist(int x,int y)
{return dis[x]+dis[y]-(dis[lca(x,y)]<<1);}
int tn3;
#define tn tn3
void find(int u)
{tn=0;while(u){st[++tn]=u;u=t[u].f;}}
ll ans;
#define chk2(u) t[t[u].f].c*4 <= t[u].c*5
void add(int u)
{
  find(u);
  for (int i=1;i<=tn;i++)t[st[i]].c++;
  int reb=0;
  for (int i=tn-1;i;i--)
    if (chk2(st[i]))
      {reb=st[i+1];break;}
  if (reb){
    tef=ef+(t[reb].c<<2)+10;
    for (int i=tn;st[i]!=reb;i--)vis[st[i]]=tef;
    int rt=grt(reb);
    t[rt].f=t[reb].f;swap(T2[rt],T2[reb]);
    build(rt,t[reb].d);
    ef=tef;
    find(rt);
    for (int i=2,v,len;i<=tn;i++){
      v=st[i];
      len=(d[t[v].d][u]=dist(v,u))-r[u];
      T[v].add(len);T2[st[i-1]].add(len);
    }find(u);
  }else {
    t[u].d=t[t[u].f].d+1;
    for (int i=2,v,len;i<=tn;i++){
      v=st[i];
      len=(d[t[v].d][u]=dist(v,u))-r[u];
      T[v].add(len);T2[st[i-1]].add(len);
    }T[u].add(-r[u]);
  }
  for (int i=tn,v,len;i>1;i--){
    len=r[u]-d[t[v=st[i]].d][u];
    ans+=T[v].rnk(len)-T2[st[i-1]].rnk(len);
  }
}
#undef tn
int n;
int main()
{
  read();vis[0]=INF;ms[0]=(n=read())+1;
  read();read();puts("0");
  T[1].add(-(r[1]=read()));
  t[1].c=1;dep[1]=1;
  for (int i=2,u,c,len;i<=n;i++){
    t[i].f=f[i][0]=u=read()^(ans%1000000000);
    adl(u,i,len=read());
    dis[i]=dis[u]+len;
    dep[i]=dep[u]+1;
    r[i]=read();
    for (int j=1;j<17;j++)
      f[i][j]=f[f[i][j-1]][j-1];
    add(i);
    printf("%lld\n",ans);
  }return 0;
}