题目大意: 多组数据, 每组数据给一张图, 多组询问, 每个询问给一个点集, 要求删除一个点, 使得至少点集中的两个点互不连通, 输出方案数
题解: 圆方树, 发现使得两个点不连通的方案数就是它们路径上的原点个数. 如何处理重复? 可以按圆方树的 $dfn$ 序排序, 相邻两点求一下贡献, 这样贡献就被重复计算了两次, 除去 $k$ 个询问点就行了. 还有每次计算中 $lca$ 没有被统计, 发现排序后第一个点和最后一个点的 $lca$ 一定是深度最浅的, 所以只有这个点没有被统计答案, 加上即可
卡点: 1. 圆方树 $dfn$ 数组没赋值
2.$LCA$ 的 $log$ 太小
- C++ Code:
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #define maxn 200010
- #define maxm 200010
- int Tim, n, m, LCA;
- inline int min(int a, int b) {return a <b ? a : b;}
- inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}
- struct Tree {
- #define root 1
- #define fa(u) dad[u][0]
- #define M 18
- int head[maxn], cnt;
- struct Edge {
- int to, nxt;
- } e[maxm << 1];
- inline void addE(int a, int b) {e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;}
- inline void add(int a, int b) {
- addE(a, b);
- addE(b, a);
- }
- int dad[maxn][M], dep[maxn], sz[maxn];
- int dfn[maxn], idx;
- void dfs(int u = root) {
- dfn[u] = ++idx;
- for (int i = 1; i < M; i++) dad[u][i] = dad[dad[u][i - 1]][i - 1];
- for (int i = head[u]; i; i = e[i].nxt) {
- int v = e[i].to;
- if (v != fa(u)) {
- sz[v] = sz[u] + int(v <= n);
- dep[v] = dep[u] + 1;
- fa(v) = u;
- dfs(v);
- }
- }
- }
- inline int LCA(int x, int y) {
- if (dep[x] < dep[y]) swap(x, y);
- for (int i = dep[x] - dep[y]; i; i &= i - 1) x = dad[x][__builtin_ctz(i)];
- if (x == y) return x;
- for (int i = M - 1; ~i; i--) if (dad[x][i] != dad[y][i]) x = dad[x][i], y = dad[y][i];
- return fa(x);
- }
- inline int len(int x, int y) {
- return sz[x] + sz[y] - (sz[::LCA = LCA(x, y)] << 1);
- }
- inline void init() {
- memset(head, 0, sizeof head); cnt = 0;
- memset(dfn, 0, sizeof dfn); idx = 0;
- sz[root] = 0;
- }
- #undef root
- #undef fa
- #undef M
- } T;
- struct Graph {
- #define root 1
- int head[maxn], cnt;
- struct Edge {
- int to, nxt;
- } e[maxm << 1];
- inline void addE(int a, int b) {e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;}
- inline void add(int a, int b) {
- addE(a, b);
- addE(b, a);
- }
- int DFN[maxn], low[maxn], idx, CNT;
- int S[maxn], top, tmp;
- void tarjan(int u = root) {
- DFN[u] = low[u] = ++idx;
- S[++top] = u;
- for (int i = head[u]; i; i = e[i].nxt) {
- int v = e[i].to;
- if (!DFN[v]) {
- tarjan(v);
- low[u] = min(low[u], low[v]);
- if (low[v]>= DFN[u]) {
- CNT++;
- T.add(CNT, u);
- do {
- T.add(CNT, tmp = S[top--]);
- } while (tmp != v);
- }
- } else low[u] = min(low[u], DFN[v]);
- }
- }
- inline void init(int n) {
- memset(head, 0, sizeof head); cnt = 0;
- memset(DFN, 0, sizeof DFN); idx = 0;
- CNT = n;
- }
- #undef root
- } G;
- #define Online_Judge
- #define read() R::READ()
- #include <cctype>
- namespace R {
- int x;
- #ifdef Online_Judge
- char *ch, op[1 <<26];
- inline void init() {
- fread(ch = op, 1, 1 << 26, stdin);
- }
- inline int READ() {
- while (isspace(*ch)) ch++;
- for (x = *ch & 15, ch++; isdigit(*ch); ch++) x = x * 10 + (*ch & 15);
- return x;
- }
- #else
- char ch;
- inline int READ() {
- ch = getchar();
- while (isspace(ch)) ch = getchar();
- for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
- return x;
- }
- #endif
- }
- int s[maxn];
- inline bool cmp(int a, int b) {return T.dfn[a] < T.dfn[b];}
- int main() {
- #ifdef Online_Judge
- R::init();
- #endif
- Tim = read();
- while (Tim --> 0) {
- G.init(n = read()), T.init();
- for (int i = m = read(); i; i--) G.add(read(), read());
- G.tarjan();
- T.dfs();
- int Q = read();
- while (Q --> 0) {
- int k = read(), ans = 0;
- for (int i = 0; i <k; i++) s[i] = read();
- std::sort(s, s + k, cmp);
- s[k] = s[0];
- for (int i = 0; i < k; i++) ans += T.len(s[i], s[i + 1]);
- printf("%d\n", (ans>> 1) - k + int(LCA <= n));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2768975.html