bzoj5329: [Sdoi2018]战略游戏
Description
省选临近，放飞自我的小Q无心刷题，于是怂恿小C和他一起颓废，玩起了一款战略游戏。 这款战略游戏的地图由n个城市以及m条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到 任意其他城市。现在小C已经占领了其中至少两个城市，小Q可以摧毁一个小C没占领的城市，同时摧毁所有连接这 个城市的道路。只要在摧毁这个城市之后能够找到某两个小C占领的城市u和v，使得从u出发沿着道路无论如何都不 能走到v，那么小Q就能赢下这一局游戏。 小Q和小C一共进行了q局游戏，每一局游戏会给出小C占领的城市集合S 你需要帮小Q数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。
Input
第一行包含一个正整数T，表示测试数据的组数， 对于每组测试数据， 第一行是两个整数n和m，表示地图的城市数和道路数， 接下来m行，每行包含两个整数u和v~(1<=u<v<=n) 表示第u个城市和第v个城市之间有一条道路，同一对城市之间可能有多条道路连接， 第m+1是一个整数q，表示游戏的局数， 接下来q行，每行先给出一个整数|S|(2<=|S|<=n) 表示小C占领的城市数量，然后给出|S|个整数s1,s2,…s|S|,(1<=s1<s2<s|S|<=n)，表示小C占领的城市。 1<= T<= 10， 2<= n<= 10^5 且 n-1<= m<= 210^5， 1<= q<= 10^5， 对于每组测试数据，有Sigma|S|<= 210^5
Output
对于每一局游戏，输出一行，包含一个整数，表示这一局游戏中有多少个城市在小Q摧毁之后能够让他赢下这一局游戏。
Sample Input
2 7 6 1 2 1 3 2 4 2 5 3 6 3 7 3 2 1 2 3 2 3 4 4 4 5 6 7 6 6 1 2 1 3 2 3 1 4 2 5 3 6 4 3 1 2 3 3 1 2 6 3 1 5 6 3 4 5 6
Sample Output
0 1 3 0 1 2 3
分析
单单考虑一组询问。 如果是两个点，就是圆方树路径上圆点个数。 多个点就是圆方树上所有点路径的并的圆点个数。 显然还是一颗树，所以采用虚树。 不用建出虚树，只需要在建虚树的过程中顺便算一下距离即可。 多组数据差评。
代码
#include<bits/stdc++.h>
const int N
= 2e5 + 10, M
= 4e5 + 10;
int ri() {
char c
= getchar(); int x
= 0, f
= 1; for(;c
< '0' || c
> '9'; c
= getchar()) if(c
== '-') f
= -1;
for(;c
>= '0' && c
<= '9'; c
= getchar()) x
= (x
<< 1) + (x
<< 3) - '0' + c
; return x
* f
;
}
int di
[N
], in
[N
], n
, tot
;
struct Edge
{
int to
[M
], nx
[M
], pr
[N
], tp
;
void add(int u
, int v
) {to
[++tp
] = v
; nx
[tp
] = pr
[u
]; pr
[u
] = tp
;}
void adds(int u
, int v
) {add(u
, v
); add(v
, u
);}
void Clr() {memset(pr
, 0, sizeof(pr
)); tp
= 0;}
};
struct Round_Sqare_Tree
{
Edge T
; int fa
[N
], de
[N
], sz
[N
], ds
[N
], d
[N
], tot
;
void Clr() {T
.Clr(); tot
= 0;}
void dfs1(int u
, int ff
) {
fa
[u
] = ff
; de
[u
] = de
[ff
] + 1; di
[u
] = di
[ff
] + (u
<= n
);
sz
[u
] = 1; ds
[u
] = 0; in
[u
] = ++tot
;
for(int i
= T
.pr
[u
], v
; i
; i
= T
.nx
[i
])
if((v
= T
.to
[i
]) != ff
)
dfs1(v
, u
), sz
[u
] += sz
[v
], sz
[ds
[u
]] < sz
[v
] ? ds
[u
] = v
: 0;
}
void dfs2(int u
, int c
) {
d
[u
] = c
; if(!ds
[u
]) return ; dfs2(ds
[u
], c
);
for(int i
= T
.pr
[u
]; i
; i
= T
.nx
[i
])
if(T
.to
[i
] != fa
[u
] && T
.to
[i
] != ds
[u
])
dfs2(T
.to
[i
], T
.to
[i
]);
}
int Lca(int u
, int v
) {
for(;d
[u
] != d
[v
]; u
= fa
[d
[u
]]) de
[d
[u
]] < de
[d
[v
]] ? u
^= v
^= u
^= v
: 0;
return de
[u
] < de
[v
] ? u
: v
;
}
}rst
;
struct Tarjan
{
Edge G
; int st
[N
], dfn
[N
], low
[N
], tp
, tm
;
void Clr() {
G
.Clr(); tm
= tp
= 0;
memset(dfn
, 0, sizeof(dfn
));
memset(low
, 0, sizeof(low
));
memset(st
, 0, sizeof(st
));
}
void dfs(int u
, int ff
) {
st
[++tp
] = u
; dfn
[u
] = low
[u
] = ++tm
;
for(int i
= G
.pr
[u
], v
; i
; i
= G
.nx
[i
])
if((v
= G
.to
[i
]) != ff
) {
if(!dfn
[v
]) {
dfs(v
, u
); low
[u
] = std
::min(low
[u
], low
[v
]);
if(low
[v
] >= dfn
[u
])
for(rst
.T
.adds(u
, ++tot
); st
[tp
+ 1] != v
;)
rst
.T
.adds(st
[tp
--], tot
);
}
else low
[u
] = std
::min(low
[u
], dfn
[v
]);
}
}
}tar
;
bool cmp(int a
, int b
) {return in
[a
] < in
[b
];}
struct Itree
{
int st
[N
], h
[N
], k
, r
, rt
, tp
;
void Up(int u
, int v
) {r
+= di
[v
] - di
[u
];}
void Ins(int u
) {
if(tp
<= 1) return void(st
[++tp
] = u
);
int c
; if((c
= rst
.Lca(u
, st
[tp
])) == st
[tp
]) return void(st
[++tp
] = u
);
for(;tp
> 1 && in
[st
[tp
- 1]] >= in
[c
]; --tp
) Up(st
[tp
- 1], st
[tp
]);
if(c
!= st
[tp
]) Up(c
, st
[tp
]), st
[tp
] = c
;
st
[++tp
] = u
;
}
void Build() {
std
::sort(h
+ 1, h
+ k
+ 1, cmp
); rt
= st
[tp
= 1] = rst
.Lca(h
[1], h
[k
]);
for(int i
= 1;i
<= k
; ++i
) Ins(h
[i
]);
for(;--tp
;) Up(st
[tp
], st
[tp
+ 1]);
}
void Work() {
k
= ri(); for(int i
= 1;i
<= k
; ++i
) h
[i
] = ri();
Build(); printf("%d\n", r
+ (rt
<= n
) - k
); r
= 0;
}
}it
;
int main() {
for(int T
= ri();T
--;) {
tar
.Clr(); rst
.Clr();
tot
= n
= ri(); for(int m
= ri();m
--;) tar
.G
.adds(ri(), ri());
tar
.dfs(1, 0); rst
.dfs1(1, 0); rst
.dfs2(1, 1);
for(int q
= ri();q
--;) it
.Work();
}
return 0;
}
