2077

注意到虽然图比较稠密，但是我们可以只保留一些有用的边。先考虑一个弱化版，找到一些有效的边构成的 \(G'\) 使得 \(G\) 与 \(G'\) 连通性相同，实际上如果我们按某个坐标进行扫描线，原问题相当于维护一个集合 \(S\)，支持： \(1.\) 动态在 \(S\) 集合中加删点。 \(2.\ ......

P7710 [Ynoi2077] stdmxeypz 题解 我的第一道 Ynoi 题，体验感不高，调了大半天，最后发现有个地方 \(B_1\) 写成 \(B_2\) 了。 分析 树上问题，明显是要转到树下的，所以 DFS 序是一定要求的。 有关树上距离，所以 \(deep\) 数组也是一定要求的。 ......