又是一次不可写的题目
给一棵以1为根的有根树,开始只有1有标记.
每次操作可以给某个点打上标记,或者询问从某个点开始向上跳,遇到的第一个有标记的点.
\(n \le 10^6 , m \le 10^6\)
题目叫树链剖分，看了看提貌似真的可以树链剖分，就真写了树链剖分……给当前节点的子树全部染上当前这个节点的编号……但我可能没有考虑先到先算先来的，题目意思是只会找最下面的，而我的算法如果更新这个点，那么它的子树都会被影响。然而这显然是错的，因为如果下面有点被标记的话先返回的应该是更靠近下面的。
时间上不稳定算法
就是树链剖分……在神仙机器和神仙数据下，勉强可以卡过去
std
考虑并查集
仔细分析性质, 如果一个点 x 从始至终都没有被标记, 就可以把 \(x\) 合并到 \(x\) 的父亲上去.
于是可以离线下来后倒着做, 将加标记变为删标记.
若一个点没有标记了, 就用并查集将它和它的父亲合并.
查询时直接在并查集中询问即可.
使用路径压缩来实现并查集, 时间复杂度 \(O(m log n)\) , 期望得分 \(100\) 分.
一共n个人（\(n \le 10^1000\)）
每个人到来时会选择离当前有人位置最远的位置
问最少多少个位置满足条件
第一个人在第一个位置，第二个人就再末尾，第三个再正中间，以此类推
乱搞，然后高精度，成功爆炸
打表找规律……
\(f(x) = x + 2^{1+[\log_{2}{x?2}]}\)
然后瞎搞高精度……
给定一个正整数 \(k\) ,以及一棵 \(n\) 个节点的以 \(1\) 为根的有根树,边有长度.
记 \(LCA(a,b)\) 表示 \(a\) 与 \(b\) 在树上的最近公共祖先, \(dist(a)\) 表示树根到 \(a\) 的距离.
每个节点可以是黑色或白色,初始时每个节点的颜色为白色.
进行 \(m\) 次操作,每次操作是以下两种形式之一:
修改操作:给出一个修改节点 \(x\) ,将节点 \(x\) 染上黑色.保证 \(x\) 在染色前为白色.
询问操作:给出一个询问节点 \(x\) ,记所有黑点形成的集合为 \(S\) ,求出下面式子的值:
其中函数 \(F\) 定义为,
由于答案可能很大,只需要输出答案对 \(P=998244353\) 取模的结果.
原文：https://www.cnblogs.com/ztz-cpp/p/12682648.html