[BZOJ-2002]弹飞绵羊

Description

有n个装置，在第i个装置上会被弹到第i+X[i]个装置上，弹到大于n的装置即视为弹飞。
询问操作询问在一个装置弹几次会被弹飞，修改操作会修改X值。

有时我们需要用一种数据结构去维护树形结构，并且支持删边加边操作。
这时我们就需要用到LCT了。

给你一棵n个点的树，m次询问。
每次询问给出一些关键点，树上所有的点被距离它最近的关键点管辖，求每个关键点管辖多少点。
n ≤ 300000, m ≤ 300000, Sigma(关键点个数) <= 300000

给你一棵n个点的树，每条边上有边权。
有m次询问，每次询问都给出一些关键点。你要割掉一些边，使得从1出发无法到达这些关键点。
求割掉边的边权总和最小值。
n ≤ 250000, m ≥ 1, Sigma(关键点个数) ≤ 500000

有些问题一次询问需要O(n)的复杂度，但多次询问时间复杂度会很大。
但如果我们只需要用到题目中给出的一些关键点和它们的LCA，并且给出的关键点个数总和并不多，我们可以求出它们的LCA，建成虚树，一次询问就变成了O(关键点个数)

Wizard Cowboy终于有自己的博客啦

搞了半天终于基本成型了。。。