题意有一棵 $n(\le 3\times 10^5)$ 个点的树和 $m(\le 3\times 10^5)$ 条路径，可以把一条边的边权改为 $0$ ，求所有路径长度最大值的最小值。题解求最大的最小值，可以二分答案 $mid$ 。可以发现如果路径的长度 $> mid$ ，那么路径上一定有一条边要被修改。所以修改的这条边需要覆盖所有长度 $> mid$ 的路径，并且边权要 $\g...
题意给出一个无向图，有下列操作：$(1,a,b)$ ，查询 $a\rightarrow b$ 路径上桥的数量$(0,a,b)$ ，删除边 $(a,b)$ 。保证无论航线如何被破坏，任意时刻任意两点都能够相互到达。其中点数 $N\le 30000$ ，边数 $M\le 100000$ ，操作数 $Q\le 40000$ 。题解显然，桥的数量就是缩完点后两点间的树上距离，动态询问树上距离显然就是...
题意给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问，求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ，询问数 $M\le 50000$ 。...
题意给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(l r z)}$ 的询问，求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。其中点数 $N\le 50000$ ，询问数 $M\l...
题意一棵树，每个节点有权值和信仰值。旅行时只在与起点信仰相同的节点停留，并获得权值。有如下操作：单点修改信仰值单点修改权值查询 $(x,y)$ 路径上权值和查询 $(x,y)$ 路径上权值最大值其中节点数 $N\le 100000$ ，操作数 $M\le 100000$ ，宗教个数 $C\le 100000$ 。题解显然每个宗教需要单独维护，但每个宗教开个线段树空间要爆，所以用动态开点线段树...
这道题做法还是比较容易想到的，就是码量有点大。不严格次小生成树的思路就是先得到最小生成树，然后枚举每一条不在树里的边，找到所构成的环上权值最大的边替换掉。而这道题要求严格次小，那么权值最大的边就不能与枚举的边权值相同，如果相同就替换环上次大的边即可。我还是敲了树剖，对于最大和次大边我用pair来存，可能是STL的缘故不开O2只有90。在合并（线段树合并和lca两侧合并）时对最大和次大的处理如...
题意给一棵有 $n$ 个节点的树，然后再连 $m$ 条不重合的附加边，可以删除一条树边和一条附加边，问有多少种删除方法可以使树断裂。题解显然，每次加一条边以后树上一定会形成环，这个环任意断附加边就可以形成树，而树上任意断一条边就可以使树断裂。但是有可能会形成很多有重叠部分的环，这样按照上述方法不一定可以让树断裂。所以我们可以对每一条树边 $i$ 记录包含它的环的个数 $f[i]$ ，然后进行...
这道题应该是迄今为止我做的时间跨度最久的题，在2018.5.17第一次提交，直到今天（2019.1.26）才终于AC。题意就是给你一棵树，起初所有节点上的数是 $0$ ，对于每次操作 $(a,b,c)$ ，把 $a$ 和 $b$ 及之间的节点全部加上 $c$ ，最后输出每个节点上的数。其实题本身很简单，就是一道裸的树剖，但是有多组数据，所以一定要记得清空数组！！！需要被清空的数组：前向星的边...
第一次写树剖没看题解A题，发现题解洛谷题解区大佬里竟然没有一个做法一样的，实在是太激动了树剖学习：https://llf0703.com/p/shu-lian-pou-fen.html方法裸树剖，直接用线段树维护每一段区间中被标记的最深的节点就行了。先全部赋值为-1，然后向上传递时直接取两段中的最大值即可（因为越深的点dfs序越大）还有需要注意的是查询中在链上往上跳时只要找到了有标记的节点就...
作为一个上个月刚学完线段树的蒟蒻，看Splay又看不懂，便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了，便去花了一天学了一个Tarjan求LCA（然而后来发现并不怎么需要），然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。准备工作链表/链式前向星线段树/树状数组/Splay等可以维护一段数据的数据结构LCA （其实只涉及到一些思想，而且几乎用不...