树上差分可以用线性的复杂度处理树上路径的修改，最后通过树上前缀和还原出每个点的权值，在这种情况下它比树链剖分的复杂度更优。

树形 DP 的主要思想是在树上对每个结点设计状态，并且父结点的状态可以从子结点转移。

由于位运算的各位都是相互独立的，所以在处理位运算问题的时候可以考虑把每一位单独拆开处理。特别地，对于异或操作，通过前缀和的思想，加上异或的自反性（一个数异或自己结果为零），我们可以在预处理后在常数时间内求出来一段区间的异或值。

基环树是一个环上挂着若干颗树，通常是断环上一条边然后分类讨论，转为树上问题。

仙人掌图 圆方树是来解决仙人掌图的问题的，其中任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。 对于一个环，一定在一个边双中，但是一个边双并不一定只包含一个环，所以我们不能简单的只求出来边双算完。可以把下面的图输入 Graph Editor 观察，这整个图是边双，但是包含两个环，所以我们在 Tarjan 求的时候需要做一些处理。 1234567891011123451 22 33 11 ...

[USACO03FALL] Popular Cows G 每一头牛的愿望就是变成一头最受欢迎的牛。 现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。 这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。 你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。 题目链接：P2341，A ...

边的分类 这里先讨论关于边的几种分类，参考《算法导论》给出的定义。 树边：如果结点 vvv 是因算法对边 (u,v)(u,v)(u,v) 的探索而首先被发现，则 (u,v)(u, v)(u,v) 是一条树边。 前向边：将结点 uuu 连接到其在 DFS 树中一个后代结点 vvv 的边 (u,v)(u,v)(u,v)，树边就是一种特殊的前向边。 后向边：将结点 uuu 链接到其在 DFS 树中一个 ...

模板 给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。 若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。 题目链接：AcWing 848。 本题就是要按照入度由小到大排序。 1234567891011 ...

[HEOI2013] Segment 要求在平面直角坐标系下维护两个操作： 在平面上加入一条线段。记第 iii 条被插入的线段的标号为 iii。 给定一个数 kkk，询问与直线 x=kx = kx=k 相交的线段中，交点纵坐标最大的线段的编号。 本题输入强制在线。 输入的第一行是一个整数 nnn，代表操作的个数。 接下来 nnn 行，每行若干个用空格隔开的整数，第 i+1i + 1i+1 行 ...

归并排序求逆序对 由于我们得到的 q[l∼mid],q[mid+1∼r]q[l\sim mid],q[mid+1\sim r]q[l∼mid],q[mid+1∼r] 都是升序排列的，因此只要出现 q[i]>q[j]q[i]>q[j]q[i]>q[j] 就说明 i∼midi\sim midi∼mid 都与 q[j]q[j]q[j] 构成逆序。 1234567891011121314 ...