简介 树形 DP 的主要思想是在树上对每个结点设计状态，并且父结点的状态可以从子结点转移。 树的直径 给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。 现在请你找到树中的一条最长路径。 换句话说，要找到一条路径，使得使得路径两端的点的距离最远。 注意：路径中可以只包含一个点。 题目链接：AcWing 1072。 两次最长路（不含负权边） 任选一点 aaa ...

简介 由于位运算的各位都是相互独立的，所以在处理位运算问题的时候可以考虑把每一位单独拆开处理。 特别地，对于异或操作，通过前缀和的思想，加上异或的自反性（一个数异或自己结果为零），我们可以在预处理后在常数时间内求出来一段区间的异或值。 假设 SiS_iSi​ 是 aia_iai​ 的前缀异或值，那么求区间 [l,r][l,r][l,r] 的异或值就是 Sr⊕Sl−1S_r\oplus S_{l-1 ...

[IOI2008] Island 你准备浏览一个公园，该公园由 NNN 个岛屿组成，当地管理部门从每个岛屿 iii 出发向另外一个岛屿建了一座长度为 LiL_iLi​ 的桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制： 可以自行挑选一个岛开始游览。 任何一个岛都不能游览一次以上。 无 ...

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

由于 FFT 需要用到大量的浮点运算，既耗时间也会造成精度问题，所以就有了 NTT，利用原根与单位根相似的性质来做到加速求多项式积的目的。

用点表示法可以 O(n) 的复杂度内求出多项式之积，FFT 可以在 O(nlog(n)) 的复杂度内在多项式的点表示法和系数表示法之间转换。

受欢迎的牛（强连通分量） 每一头牛的愿望就是变成一头最受欢迎的牛。 现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。 这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。 你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。 题目链接：AcWing 1174。 也就是在缩点后的出 ...

边的分类 这里先讨论关于边的几种分类，参考《算法导论》给出的定义。 树边：如果结点 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 行 ...