原题：https://qoj.ac/problem/8557
弱化版：https://www.luogu.com.cn/problem/P7830
但是弱化版要求做到更优复杂度，但是没有修改。
本文的 参考文章
钦定树以 \(1\) 为根。钦定所有点 \(u\neq 1\) 的 \(e,t\) 循环位移成 \(e_{u,k_u-1}=fa_u\)，就是把父亲丢到最后。
首先这东西一定是有循环的。
通过一定画图观察，我们知道当一个点 \(u\) 的 \(t_u=0\) 的时候，则 \(fa_u\to u\to \cdots \to u\to fa_u\) 后 \(t\) 仍然不变，于是从 \(t\) 走出的顺序就相对固定。
- 称一时刻 \(t_u=0\) 的 \(u\) 是 好点。
并且走到过一个点 \(u\) 返回父亲后，\(u\) 一定变成了 好点。
于是当遍历过所有点之后，一定是按照树的欧拉序循环走，循环节长度为 \(2(n-1)\)。
把无向边拆成有向边，称最终树的欧拉序 遍历的边 为 \(\left(E_1,E_2,\cdots ,E_{2(n-1)}\right)\)。
- 注意这里欧拉序 \(1\) 往儿子遍历的顺序就是初始 \(e_{1,t_1},e_{1,t_{1}+1},\cdots\) 的顺序。
在这之前呢？
称 一轮 为当前从 \(1\) 出发返回 \(1\)，并且 \(t_1\) 不变（即 \(1\) 的所有儿子都遍历过了）所走过的 边序列。观察每轮的性质。
- 每轮走的序列都是 \(E\) 的子序列。
- 上一轮走的序列一定是这一轮的子序列。
相当于是逐轮做一个增广，每轮会多拉一些子节点进序列，使得它们变好。
最终所有节点变好，就增广成了 \(E\) 序列。
- 注：在增广成 \(E\) 后我们延续一轮的定义，即之后每轮都走了一个 \(E\) 序列。
- 我们根据 轮 对这个问题进行了很好的阶段划分，接下来刻画每一轮是怎么走的。
设点 \(u\) 在第 \(f_u\) 轮首次被加入边序列（中的一个端点），按欧拉序排序后第 \(i\) 条边在第 \(g_i\) 轮边首次被加入边序列。
\(f_u\) 就考虑它要么在 \(f_{fa_u}\) 轮就走到了，要么在 \(fa_u\) 变好后下一轮走到。
于是就考虑令 \((u,v=fa_u)\) 的边权为初始 \(v\) 是否不能 一步走到 \(u\)，则 \(f_u\) 就是 \(u\) 的深度。
\(g\) 根据 \(f\) 容易求出。即 \(g(u\to v)=f(v)\)。
然后前 \(x\) 轮走过的边数就是 \(\sum\limits_{i=1}^{2n-2} \max(x-g_i+1,0)\)。
然后每轮走的顺序就是 \(g_i\le x\) 的所有 \(i\) 拎出来，在欧拉序上的顺序。
于是静态我们就很好做了，二分出轮数。然后每轮二分求出走到哪即可。
动态我们注意到修改一个点的 \(t\)，其实不改变 \(E\) 这个欧拉序！
所以原来的大部分性质得以保留。
修改 \(t_x\) 只影响对于 \(f\) 我们刻画的边权，即把若干到儿子边 \(x\to e_{x,[l,r]}\) 的 \(01\) 边权修改了一下。
然后修改的儿子是连续的，于是对子树的影响就是欧拉序的一个区间。
于是修改的影响相当于对于 \(g\) 的一个区间 \(\pm 1\)。
现在数据结构维护。
然后比如要维护 \(\sum \max(x-g_i+1,0)\)，就是要维护 \(\le x\) 的 \(g_i\) 个数和 \(g_i\) 的和。