树链剖分
漆子超《分治算法在树的路径问题中的应用》
可以求出一个序列，既是DFS序，又是轻重链的序列
子树第 k 大
树链剖分 DFS序列
树链剖分 DFS序列
树链剖分 维护颜色段数
树上维护最大子段和
一个特殊的做法： 启发式合并 + 暴力
另一个特殊的做法： Kruskal合并时就回答两个集合询问的交集
上一题的基础上维护次小，就不能用投机取巧的方法了
离线，问子树内向外连边中权值最小是多少
并查集，维护有没有洞
虚树，树上差分
删一条边，加一条边，最小化树的直径
有趣的计数题
中心点：度数 >= 3的点
一个中心点，空2个的情况
(n - 2)! / (距离中心点的边数 <= 1的点的个数 - 2)!
一个中心点，空3个的情况
(n - 3)! / (距离中心点的边数 <= 2的点的个数 - 3)!
一个中心点，空k个的情况
(n - k)! / (距离中心点的边数 <= (k-1)的点的个数 - k)!
多个中心点的情况？
如果两个中心点之间的距离是d （之间有d条边）
那么当空位个数 >= d + 2的时候，两个中心点会合并
for (pair<int, int> j: b[n - 1 - i])
{
c[F(j.first)] += j.second;
}
for (int jj = 0; jj < b[n - 1 - i].size(); jj++)
{
pair<int, int> j: b[n - 1 - i][jj];
c[F(j.first)] += j.second;
}
map<string, double> g;
for (pair<string, double> i: g)
{
i.first // key, string
i.second // value, double
}
树的重心
树的直径
点分治
点分治或者启发式合并
动态点分治
树上需要统计所有路径
2种思路
set<int> s[10020];
void dfs(int x, int y, int d)
{
// s[x] 表示子树x中所有节点的深度（从根节点开始算）的集合
s[x].insert(d);
for (pair<int, int> i: a[x])
{
if (i.first != y)
{
dfs(i.first, x);
if (s[x].size() < s[i.first].size())
{
s[x].swap(s[i.first]);
}
枚举所有询问
{
if (这个询问已经被回答了)
{
continue;
}
for (int j: s[i.first])
{
if (s[x].find(询问的长度 + 2 * d - j) != s[x].end())
{
找到了
}
}
}
for (int j: s[i.first])
{
s[x].insert(j);
}
}
}
}
可以在 n log n 的时间内回答一个询问