「题解」洛谷 P8339 [AHOI2022] 钥匙

暴力：走 \(u\to v\) 路径时，遇到一个钥匙，将其压入对应颜色的栈，遇到一个宝箱，将栈顶的钥匙和其匹配，弹出这个钥匙。

特殊性质 A：考虑一个钥匙 \(x\) 及其对应的宝箱 \(y\)，会对所有包含 \(x\to y\) 的路径（这里的包含要求和 \(x\to y\) 是一个方向），都会产生 \(1\) 的贡献。那么考虑在 \(dfn\times dfn\) 平面上，\((x,y)\) 代表的是 \(x\to y\) 对应的答案，每一个钥匙及其宝箱所对应的路径 \(x\to y\)，根据 \(x,y\) 是否为祖先关系的不同，包含其的路径是子树补 \(\times\) 子树的矩形，或者子树 \(\times\) 子树补的矩形，或者子树 \(\times\) 子树的矩形。那么问题就变成了矩形 \(+1\)，单点求值问题，用树状数组扫描线即可。

正解考虑借鉴上面两个做法的思想。

考虑一次暴力的贪心匹配的过程，一个钥匙和哪个宝箱匹配，和这个钥匙之前遇到的钥匙以及它们的匹配情况是无关的。所以对每个钥匙考虑，其贪心匹配过程中，往各个方向走，匹配到的宝箱集合是一定的。

暴力找出这个集合的过程就是，以这个钥匙 \(x\) 为根 dfs，维护一个栈，只存与根颜色相同的钥匙，然后匹配。直到有宝箱 \(y\) 和根代表的钥匙匹配成功了，那么 \(x\to y\) 会对所有包含 \(x\to y\) 的路径产生一个 \(1\) 的贡献，这里用特殊性质 A 的扫描线解决即可。

由于 dfs 的过程中只和同一颜色有关，所以把同一颜色的拉出来，在虚树上 dfs 找宝箱即可。

时间复杂度 \(\mathcal{O}(n\log n)\)．

#include
#include
#include
#include
#include
#include
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<