干事儿网网站开发,建设 网站,广州外贸公司排名前十,如何做网站发布商品题意#xff1a;给一张 nnn 点 mmm 边的连通无向图#xff0c;qqq 次询问#xff0c;每次给出一个点集 SSS #xff0c;求有多少个不在 SSS 中的点满足删除后 SSS 中存在两个点不连通。 n≤105,m≤2105,∑∣S∣≤2105n\leq 10^5,m\leq 2\times 10^5,\sum |S|\leq 2\times 1…题意给一张 nnn 点 mmm 边的连通无向图qqq 次询问每次给出一个点集 SSS 求有多少个不在 SSS 中的点满足删除后 SSS 中存在两个点不连通。
n≤105,m≤2×105,∑∣S∣≤2×105n\leq 10^5,m\leq 2\times 10^5,\sum |S|\leq 2\times 10^5n≤105,m≤2×105,∑∣S∣≤2×105
显然是虚树
题目相当于求 SSS 的割点数量想到圆方树
建出圆方树后对于 SSS 中的一对点它们路径上任意一个圆点都满足条件。答案相当于求两两路径上的圆点的并集。因为不能取 SSS 中的点所以要减去 ∣S∣|S|∣S∣。
套到虚树上发现就是虚树覆盖的圆点个数。即对于每个点 uuu 设 faufa_ufau 为其虚树上的父亲sumusum_usumu 为原树上根到 uuu 的圆点个数。那么答案为 ∑(sumu−sumfau)\sum(sum_u-sum_{fa_u})∑(sumu−sumfau)。
注意要特判 lca(S)\operatorname{lca}(S)lca(S)
复杂度 O(nm∑∣S∣log∣S∣)O(nm\sum|S|\log |S|)O(nm∑∣S∣log∣S∣)
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include algorithm
#define MAXN 400005
#define MAXM 800005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
struct edge{int u,v;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
inline void addnode(int u,int v)
{e[cnt](edge){u,v};nxt[cnt]head[u];head[u]cnt;
}
int n,m;
int dfn[MAXN],low[MAXN],tim;
int stk[MAXN],tp,vis[MAXN],bcc[MAXN],vcnt;
vectorint rtt[MAXN];
void tarjan(int u)
{dfn[u]low[u]tim;for (int ihead[u];i;inxt[i]){if (!vis[i1]!bcc[i1]) vis[(stk[tp]i)1]1;if (!dfn[e[i].v]){tarjan(e[i].v);low[u]min(low[u],low[e[i].v]);if (dfn[u]low[e[i].v]){rtt[u].push_back(bcc[i1]vcnt);rtt[bcc[i1]].push_back(u);while (vis[i1]){int tstk[tp--];vis[t1]0;rtt[bcc[t1]vcnt].push_back(e[t].v);}}}else low[u]min(low[u],dfn[e[i].v]);}
}
int sum[MAXN],dep[MAXN],fa[MAXN][20];
void dfs(int u)
{dfn[u]tim;for (int i1;i20;i) fa[u][i]fa[fa[u][i-1]][i-1];for (int i0;i(int)rtt[u].size();i)if (!dep[rtt[u][i]]){dep[rtt[u][i]]dep[u]1;sum[rtt[u][i]]sum[u](rtt[u][i]n);fa[rtt[u][i]][0]u;dfs(rtt[u][i]); }
}
inline int lca(int x,int y)
{if (dep[x]dep[y]) swap(x,y);int tdep[x]-dep[y];for (int i0;(1i)t;i) if (t(1i)) xfa[x][i];if (xy) return x;for (int i19;i0;i--) if (fa[x][i]!fa[y][i]) xfa[x][i],yfa[y][i];return fa[x][0];
}
int lis[MAXM],len;
inline bool cmp(const int x,const int y){return dfn[x]dfn[y];}
inline void solve()
{sort(lis1,lislen1,cmp);int reslen;for (int i1;ires;i) lis[len]lca(lis[i],lis[i1]);sort(lis1,lislen1,cmp);lenunique(lis1,lislen1)-lis-1;int ans0;tp0;for (int i1;ilen;i){while (tplca(stk[tp],lis[i])!stk[tp]) --tp;ans(tp? sum[lis[i]]-sum[stk[tp]]:(lis[i]n));stk[tp]lis[i];}printf(%d\n,ans-res);
}
int main()
{for (int Tread();T;T--){nread(),mread();cnt1;memset(head,0,sizeof(head));memset(nxt,0,sizeof(nxt));memset(bcc,0,sizeof(bcc));memset(dep,0,sizeof(dep));memset(sum,0,sizeof(sum));memset(dfn,0,sizeof(dfn));for (int i1;ivcnt;i) rtt[i].clear();timtp0;for (int i1;im;i){int u,v;uread(),vread();addnode(u,v),addnode(v,u);}vcntn;tarjan(1);for (int in1;ivcnt;i) {sort(rtt[i].begin(),rtt[i].end());rtt[i].erase(unique(rtt[i].begin(),rtt[i].end()),rtt[i].end());}dep[1]sum[1]1,tim0;dfs(1);for (int qread();q;q--){lenread();for (int i1;ilen;i) lis[i]read();solve();}}return 0;
}
