莫比乌斯函数重置版

行列式——矩阵树与 LGV

行列式

虚树速通

如果每次询问是输入树上一个点集，那么做法往往是虚树。
虚树就是把原图中所有有用的点抠出来，然后把抠出来的点建颗树，叫虚树。
那哪些点有用？b 中的点是输入的点（关键点），c 中的点是有用的点（为了可以树形 dp 不得不加入的点）。
其实虚树就相当于把一棵树中两个关键点路径间的点压缩成了很少的几个点，把不在关键点路径上的都忽略掉了。

int m;cin>>m;
b.resize(m);
for(int i=0;i<m;i++)cin>>b[i];
std::sort(all(b),[](int x,int y){
	return dfn[x]<dfn[y];
});
c=b;
for(int i=1;i<m;i++)
	c.push_back(LCA(b[i-1],b[i]));
sort(all(c),[](int x,int y){
	return dfn[x]<dfn[y];
});
c.erase(unique(all(c)),c.end());
for(int i=1;i<siz(c);i++){
	int j=LCA(c[i-1],c[i]),d=DIS(j,c[i]);
	g2[j].emplace_back(c[i],d);
	g2[c[i]].emplace_back(j,d);
}

从 tarjan 到圆方树

强连通

强连通分量：在一张有向图中，如果 $u$ 能走到 $v$，$v$ 能走到 $u$，那么 $u,v$ 在同一个强连通分量内。

求强连通分量

强连通分量缩点：将一张有向图中所有在同一个强连通分量内的点变成同一个点。缩点之后是拓扑图。

QOJ9243 Counting Multisets

给定 $n,x,y_m$，对于每个 $y<y_m$，求有多少长度为 $n$ 的数组，满足它们加起来是 $x$，或起来是 $y$ 并且这个数组的排列个数是奇数个。

wqs 二分

应用场景：恰好选 $k$ 个，凹凸性。

一维 dp 中的斜率优化与四边形不等式

斜率优化：

回滚莫队速成

正常的莫队中，我们使用 $L,R$ 两个指针的移动来框出区间 $[l,r]$，可以发现这种移动是不满足可撤销性的。
如果我们换一种指针的移动方式，使莫队具有可撤销性，那么配合可撤销数据结构就可以维护更多东西了。

整体二分的不带修写法

对于每个询问都可以二分的题目，可以将所有询问放在 vector 中。假设当前二分的答案区间为 $[l,r]$，按照比较结果把询问分成答案在左边和答案在右边，递归处理答案在左边 $[l,mid]$ 和答案在右边 $[mid+1,r]$。
但是每次都进行 check 时，需要把 $[l,r]$ 这一段的所有操作拿出来，太慢了。不妨使用类似莫队的方法，使用一个指针来辅助快速 check。

最小生成树边权期望

在一张 $n$ 个点的完全图中，每条边的权值是 $1\sim m$ 中的一个整数，求最小生成树权值的期望。