题解 P4606 【[SDOI2018]战略游戏】
liuzhangfeiabc · · 题解
圆方树上圆方果，
圆方树下你和我。
圆方树前建虚树，
欢乐多又多。
(/huaji)
继apio2018之后，圆方树再现江湖！
这里给不会圆方树的童鞋普及一下这种今年wc上的新(hei)科技：
先对一张无向图进行tarjan求点双。
什么你说你不会tarjan求点双？出门右转百度一下。
之后将原图中的点看做圆点，对每个点双新建一个节点看做方点。
然后重新建图：如果一个点在某个点双里，就将其对应的点连边。
可以证明最后得到的一定是一棵树（如果原图不连通就会得到森林）。
为什么是棵树呢？首先如果原图连通，如此操作后的图也一定连通（容易看出操作不会改变两点之间的连通关系）；其次如果新图上有环，就可以把它缩起来，形成一个更大的点双。
这棵树有什么性质呢？
1、树上的每一条边都连接了1个圆点和1个方点。
也就是说，每个圆点都与其所在的的点双有边相连，每个方点都与这个点双中包含的点相连。
这里补充一下：我们将“点双”定义为“将其中任意一个节点删去，剩下的部分依然连通”，这样定义的好处是对于2个点1条边的情况我们也将其视作一个点双，可以避免一些特殊情况的讨论。（据说不这么定义可能会出现圆点与圆点的连边……瑟瑟发抖）
2、对于所有的割点（定义为删去后使得图不连通的点），在图中都有至少2条出边（对应图中的割点至少在2个点双内）；而非割点只会有1条出边。
3、一条（从圆点到圆点的）树上简单路径代表什么？
代表原图中的一堆路径，其中：所有经过的割点（树上的圆点）都是必经的，而在点双内（树上的方点）可以随便走。
也就是说：原图中两点简单路径的并！
这样一来我们就可以用圆方树处理很多图上路径问题，例如只需要在方点处维护点双内所有点的信息就可以处理图上简单路径的并的相关问题。
这样一来我们就可以把很多树上路径问题强行上图。
以及许多序列维护区间信息的问题，原先只是上树，现在可以上图了！
而且这个东西的实现难度和代码复杂度并不大，说不定哪天变成noip基础算法呢……逃
回到这道题：
首先考虑删掉哪些点才能使得图上原本连通的两点变为不连通。
显然是两点的简单路径中必经的割点。
而这在圆方树上对应的就是两点路径上的圆点。
对于多个起点要求存在一对不连通的问题，因为询问点数的总数是O(n)级别，容易想到虚树。
将每次的询问点拎出来建虚树，我们会发现虚树上所有是非询问点的圆点（包括建虚树需要用到的关键点和虚树的边上经过的那些非关键点）都是合法的。
因此我们只要每次统计虚树上的点数即可。
复杂度只有建虚树的1个log。
顺便说一句我也不知道为什么网上的tarjan求点双都是将边入栈……我一直写的是点入栈也一直没出过锅……（可能有一些奇妙的处理保证了正确性？）
再以及，为了区分开树边和图边显得不那么乱，这里用的是孩子链表存树。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
li read(){
li x = 0;
int y = 0,c = gc;
while(!isdigit(c)){
y = c;
c = gc;
}
while(isdigit(c)){
x = (x << 1) + (x << 3) + (c ^ '0');
c = gc;
}
return y == '-' ? -x : x;
}
void print(li q){
if(q < 0){
pc('-');
q = -q;
}
if(q >= 10) print(q / 10);
pc(q % 10 + '0');
}
int t,n,m,p,s,a[200010],sl;
int lgb[200010];
struct edge{
int to,nxt;
}e[500010];
int cnt,fir[100010];
inline void ins(int u,int v){
e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
e[++cnt].to = u;e[cnt].nxt = fir[v];fir[v] = cnt;
}
int st[200010],ft;
int low[100010],dfn[100010],nw,tot,dfsnw;
int fa[200010],fsts[200010],nxt[200010];
void tar(int q,int lst){//求点双
dfn[q] = low[q] = ++nw;
st[++ft] = q;
for(int i = fir[q];i;i = e[i].nxt){
int j = e[i].to;
if(j == lst) continue;
if(dfn[j]) low[q] = min(low[q],dfn[j]);
else{
tar(j,q);
if(low[j] >= dfn[q]){
fa[++tot] = q;
nxt[tot] = fsts[q];
fsts[q] = tot;//这里是孩子链表存树
int l;
do{
l = st[ft--];
fa[l] = tot;
nxt[l] = fsts[tot];
fsts[tot] = l;
}while(l != j);
}
low[q] = min(low[q],low[j]);
}
}
}
//没错圆方树在求点双的过程中就顺手构建好了，所以我说难度并不大（逃）
//剩下的就是一些树上常规操作
int len[200010],dpt[200010];//这个len是根到某个点的路径上圆点的个数，用来最终计算答案
int stb[18][200010];
int dfsx[200010],wz[200010],ed[200010];
void dfs(int q){
dfsx[++dfsnw] = q;
wz[q] = dfsnw;
len[q] = len[fa[q]] + (q <= n);
for(int i = fsts[q];i;i = nxt[i]){
dpt[i] = dpt[q] + 1;
stb[0][i] = q;
dfs(i);
}
ed[q] = dfsnw;
}
inline bool isfa(int u,int v){
return wz[u] < wz[v] && ed[u] >= ed[v];
}
inline void buildst(){
register int i,j;
for(i = 1;i <= 17;++i){
for(j = 1;j <= n;++j) stb[i][j] = stb[i - 1][stb[i - 1][j]];
}
}
int lca(int u,int v){
if(dpt[u] < dpt[v]) swap(u,v);
int i = 0,j = dpt[u] - dpt[v];
while(j){
if(j & 1) u = stb[i][u];
j >>= 1;
++i;
}
if(u == v) return u;
for(i = lgb[dpt[v]];i >= 0;--i){
if(stb[i][u] == stb[i][v]) continue;
u = stb[i][u];
v = stb[i][v];
}
return fa[u];
}
void init(){
tot = n;
ft = 0;
tar(1,0);
dfs(1);
buildst();
}
bool cmp(int q,int w){
return wz[q] < wz[w];
}
bool vst[200010];
int st2[200010],ft2;
int main(){
//freopen("game.in","r",stdin);
//freopen("game.out","w",stdout);
int i,j,u,v,ans;
for(i = 2;i <= 200000;++i) lgb[i] = lgb[i >> 1] + 1;
t = read();
while(t--){
cnt = 0;
memset(fir,0,sizeof(fir));
memset(fa,0,sizeof(fa));
memset(fsts,0,sizeof(fsts));
memset(nxt,0,sizeof(nxt));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(wz,0,sizeof(wz));
nw = tot = dfsnw = 0;
n = read();
m = read();
for(i = 1;i <= m;++i){
u = read();
v = read();
ins(u,v);
}
init();
p = read();
while(p--){
s = read();
for(i = 1;i <= s;++i){
a[i] = read();
vst[a[i]] = 1;
}
//以下是构建虚树的部分
sort(a + 1,a + s + 1,cmp);
sl = s;
for(i = 1;i < s;++i){
j = lca(a[i],a[i + 1]);
if(!vst[j]){
a[++sl] = j;
vst[j] = 1;
}
}
sort(a + 1,a + sl + 1,cmp);
ft2 = 0;
ans = 0;
st2[0] = fa[a[1]];//便于把虚树的根算进答案
for(i = 1;i <= sl;++i){
j = a[i];
while(ft2 && !isfa(st2[ft2],j)) --ft2;
u = st2[ft2];
ans += len[j] - len[u];
st2[++ft2] = j;
}
print(ans - s);//别忘了把询问点减掉
pc('\n');
for(i = 1;i <= sl;++i) vst[a[i]] = 0;
}
}
return 0;
}
//We_cannot_live_without_our_red_sun_Claris
//2018nian5yue15riday1