My Blogs

P8990 [北大集训 2021] 小明的树

首先连通块个数可以用经典的点边转化，用点的个数减去边的条数。

观察之后可以发现定合法的充要条件是黑色的点构成一个连通块，同样使用点边转化。

现在可以看成有两个序列（时间轴），\(V\) 和 \(S\)，操作是区间 \(v\) 的修改，区间 \(s\) 的修改，和查询全局 \(v=1\) 的 \(s\) 的和。

对于一个点，设 \(p_i\) 为其出现时间，则其在 \([1,p_i-1]\) 上对 \(v\) 有 \(1\) 的贡献，在 \([p_i,n]\) 上对 \(s\) 有 \(1\) 的贡献。

对于一条边，设 \(p_1\) 为两端点出现较早的时间，\(p_2\) 为较晚点的出现时间，则其在 \([1,p_1-1]\) 上对 \(v\) 有 \(-1\) 的贡献，在 \([p_2,n]\) 上对 \(s\) 有 \(-1\) 的贡献。

容易发现操作一定保证 \(v\geq 1\)，所以线段树维护区间 \(v\) 是最小值的 \(s\) 的和，修改就直接把原来边的贡献删掉，再加入新的边。经典答案和树形态无关，复杂度是 \(\mathcal O((n+q)\log n)\)。