视频链接：E94Tarjan边双缩点+树形DPP8867[NOIP2022]建造军营_哔哩哔哩_bilibili  P8867[NOIP2022]建造军营-洛谷|计算机科学教育新生态//Tarjan边双缩点+树形DPO(n)#include<bits/stdc++.h>usingnamespacestd;intread(){intx=0,f=1;charc=getchar

P8867[NOIP2022]建造军营只有B国袭破坏的道路是无向图的割边时，这张图才会变得不连通，所以我们进行边双缩点，最终形成一棵树，不妨令根节点为\(1\)。记\(E[u]\)为缩点后的\(u\)包含多少条原图上的边，\(V[u]\)为\(u\)包含多少个原图上的点，并定义\(s[u]\)表示子树\(u\)中的边数。那么