P3950 部落冲突 题解
想练练树剖，找到了一个不像板子的板子。（题目故事情节引人入胜）
这里来记录一下树剖的一些原理。
树剖的基本原理就是把一棵很高大的树分成很多块，然后使用数据结构来维护这么多块。那么怎么分呢？我们定义对于一个节点，其儿子中的子树大小最大的那个儿子被称为这个节点的重儿子，其他儿子被称为轻儿子。那么在一棵树上，一定有很多的重儿子，我们把全部都由重儿子组成的链称为重链，都由轻儿子组成的链被称为轻链。由此一棵树被我们分成了很多条重链和很多条轻链。接着我们考虑如何维护这堆重链和轻链。
对于某个节点 ，我们定义：
以
为根的子树节点个数。
）
然后接下来的很多东西很多算法书上都有了，省掉好多字。
正式进入题解部分：
我们考虑每个操作的实质是什么：
操作 1，也就是询问，也就是询问边权和是否为 。
操作 2,3 就是修改单条边。
我们只需要维护每个节点与其父亲的连边即可。（这种点权表边权的小 trick 应该来看这篇文章的人都是会的叭）
Code:
