傳送門

---

弱化版

考慮到去掉一個點使得存在兩個點不連通的形式類似割點，不難想到建立圓方樹。那么在圓方樹上對于給出的關鍵點建立虛樹之后，我們需要求的就是虛樹路徑上所有圓點的數量減去關鍵點的數量。

因為沒有DP，所以其實沒有必要將虛樹建立起來，只需要維護一個鏈并就可以了。

#include<bits/stdc++.h> //This code is written by Itst using namespace std;inline int read(){int a = 0;char c = getchar();bool f = 0;while(!isdigit(c) && c != EOF){if(c == '-')f = 1;c = getchar();}if(c == EOF)exit(0);while(isdigit(c)){a = a * 10 + c - 48;c = getchar();}return f ? -a : a; }const int MAXN = 2e5 + 7; int head[MAXN] , N , M , cnt , cntEd , ans; int dfn[MAXN] , low[MAXN] , st[MAXN] , ts , top; int ind[MAXN] , dep[MAXN] , TS; vector < int > ch[MAXN]; int num[MAXN] , jump[MAXN][19]; struct Edge{int end , upEd; }Ed[MAXN << 1]; struct cmp{bool operator ()(int a , int b){return ind[a] < ind[b];} }; set < int , cmp > s; set < int , cmp > :: iterator it1 , it2;inline void addEd(int a , int b){Ed[++cntEd].end = b;Ed[cntEd].upEd = head[a];head[a] = cntEd; }void pop(int x , int bot){++cnt;ch[cnt].clear();ch[x].push_back(cnt);do{ch[cnt].push_back(st[top]);}while(st[top--] != bot); }void tarjan(int x , int p){dfn[x] = low[x] = ++ts;st[++top] = x;ch[x].clear();for(int i = head[x] ; i ; i = Ed[i].upEd)if(Ed[i].end != p)if(!dfn[Ed[i].end]){tarjan(Ed[i].end , x);low[x] = min(low[x] , low[Ed[i].end]);if(low[Ed[i].end] >= dfn[x])pop(x , Ed[i].end);}elselow[x] = min(low[x] , dfn[Ed[i].end]); }void dfs(int x , int p){ind[x] = ++TS;dep[x] = dep[p] + 1;jump[x][0] = p;for(int i = 1 ; i <= 18 ; ++i)jump[x][i] = jump[jump[x][i - 1]][i - 1];num[x] = num[p] + (x <= N);for(int i = 0 ; i < ch[x].size() ; ++i)dfs(ch[x][i] , x); }inline int LCA(int x , int y){if(dep[x] < dep[y])swap(x , y);for(int i = 18 ; i >= 0 ; --i)if(dep[x] - (1 << i) >= dep[y])x = jump[x][i];if(x == y)return x;for(int i = 18 ; i >= 0 ; --i)if(jump[x][i] != jump[y][i]){x = jump[x][i];y = jump[y][i];}return jump[x][0]; }inline void insert(int x){s.insert(x);it1 = it2 = s.find(x);int p = 0 , q = 0;if(it1 != s.begin())p = LCA(*(--it1) , x);if(++it2 != s.end())q = LCA(*it2 , x);p = dep[p] < dep[q] ? q : p;ans += num[x] - num[p]; }int main(){ #ifndef ONLINE_JUDGEfreopen("in","r",stdin);freopen("out","w",stdout); #endiffor(int T = read() ; T ; --T){cnt = N = read();M = read();memset(head , 0 , sizeof(head));memset(dfn , 0 , sizeof(dfn));cntEd = ts = TS = top = 0;for(int i = 1 ; i <= M ; ++i){int a = read() , b = read();addEd(a , b);addEd(b , a);}tarjan(1 , 0);dfs(1 , 0);for(int Q = read() ; Q ; --Q){s.clear();ans = 0;int S = read() , t;for(int i = 1 ; i <= S ; ++i){int a = read();if(i == 1)t = a;elseif(t != 1)t = LCA(t , a);insert(a);}printf("%d\n" , ans - S - num[jump[t][0]]);}}return 0; }

轉載于:https://www.cnblogs.com/Itst/p/10290442.html

總結

以上是生活随笔為你收集整理的Luogu4606 SDOI2018 战略游戏 圆方树、虚树、链并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。