每个点一定属于一个重链
重链条数和轻边边数是logn级别
证明和启发式合并差不多
因为轻子树的大小至少是重子树大小-1
树链剖分:两遍dfs
第一次:统计子树大小,确定重儿子
第二次:把重链剖出来
每次都走重儿子,则它的dfs序中重链是连续的一段
复杂度o(log n)
改变边权和询问路径上最大边权
把边权放到点上,把点权放到线段树中
修改的时候就是单点修改
查询最大边权的时候,就查询两条链(因为lca存的是它到它父亲这一条边的边权)上的最大值
重链-轻边-重链-轻边
找线段树上对应的区间然后查询就可以
开一个2000位的bitset
第i位是1表示标号为i的bitset可以到达他
这个scc的大小*它能到达的scc的大小之和再加起来就是答案
bitset
#include<bitset>
bitset<100000> a;
表示一个长度为100000的二进制数(下标从0开始)
bitset<100000> b;
a[1]可以取到第一位
a[0]
a[99999]=1;
a&b
a^b
a|b
a.set
a.reset
a.count(数有多少1)