[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））传送门
蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。
首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径
因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs
[luoguP2486] [SDOI2011]染色（树链剖分）传送门
就是个模板啦
记录每一个点的左端点颜色和右端点颜色和当前端点颜色段数。
合并时如果左孩子右端点和右孩子左端点不同就ans
在重链上跳的时候别忘记统计一下
—
[luoguP2146] 软件包管理器（树链剖分）传送门
看着很吓人，其实就是个树链剖分模板。
可支持操作：
1.将节点 x 到 根 的路径上的值都变成 1
2.将以节点 x 为根的子树的值都变成 0
1A爽~
——代码
1 #include
[luoguP2982][USACO10FEB]慢下来Slowing down（dfs序 + 线段树）传送门
这个题显然可以用树链剖分做。
然而线段树也能做。
每个点都对它的子树有贡献，所以先求一边 dfs序，然后直接在 dfs序 中搞 线段树 就行。
——代码
1 #include <
[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）传送门
树链剖分固然可以搞。
但还有另一种做法，可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。
而给以某一节点 x 为根的子树增
【模板】树链剖分[ZJOI2008]树的统计
洛谷传送门
第一遍树链剖分，打的很难受。
其中拉闸了，检查真是费劲。
树链剖分是什么？
树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分
lca最近公共祖先（模板）洛谷上的lca模板题——传送门
1.tarjan求lca
学了求lca的tarjan算法（离线），在洛谷上做模板题，结果后三个点超时。
又把询问改成链式前向星，才ok。
这个博客，tarjan分析的很详细。
