dfs 匹配链

__ryp__ · 2024-07-12 15:18:28 · 个人记录

一个点儿子形成的链，在整个树上只能是两种情况，要么是往上连接成一条链，要么是和儿子形成一条链。

考虑怎么实现。首先 DFS，所返回的是儿子剩下的那条链。我们把它放到 multiset 里头，每次加入的时候看里面有没有和它匹配的。如果没有就加入，否则就匹配掉。最后没匹配到的就返回。

注意 multiset.erase 不能直接删数，否则会全部删掉。要用 q.erase (q.find (x))。