LOJ #2562. 「SDOI2018」战略游戏（圆方树）

题目 这个题还是近乎板子题吧。 tarjan求点双连通分量 ， 建圆方树，路径上的圆点为必须经过的点。 那么答案就是点集中任意两点间的圆点数量，也就是在虚树上或虚树的边上的圆点数 - 虚树上的圆点数。 设点集为S,答案为按dfs序排序后： $\frac{dis(S1,S2)+dis(S2,S3)...+dis(Sk,S1)}{2}-|S|$ AC Code:

#include<bits/stdc++.h> #define maxn 200005 using namespace std; int info[maxn],Prev[maxn<<1],to[maxn<<1],cnt_e; void Node(int u,int v){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v; } vector<int>G[maxn]; int n,m,cnt_p; int dfn[maxn],low[maxn],tot,sta[maxn],R; void dfs(int now){ dfn[now] = low[now] = ++tot; sta[R++] = now; for(int i=info[now];i;i=Prev[i]) if(!dfn[to[i]]){ dfs(to[i]),low[now]=min(low[now],low[to[i]]); if(low[to[i]] >= dfn[now]){ ++cnt_p; for(int u = -1;R && u!=to[i];){ G[u = sta[--R]] . push_back(cnt_p); G[cnt_p] .push_back(u); } G[now].push_back(cnt_p) , G[cnt_p].push_back(now); } } else low[now] = min(low[now] , dfn[to[i]]); } int fa[maxn] , dep[maxn] , siz[maxn] , son[maxn] , tp[maxn] , sum[maxn] , id[maxn] , cnt; void dfs1(int now,int ff){ dep[now] = dep[fa[now] = ff] + (siz[now] = 1) , son[now] = -1; sum[now] = sum[ff] + (now<=n); for(int u:G[now]) if(u!=ff){ dfs1(u,now),siz[now]+=siz[u]; if(son[now] == -1 || siz[son[now]] < siz[u]) son[now] = u; } } void dfs2(int now,int ff){ id[now] = ++cnt; if(son[now]!=-1) tp[son[now]] = tp[now] , dfs2(son[now],now); for(int u:G[now]) if(u!=ff && u!=son[now]) tp[u] = u,dfs2(u,now); } int Lca(int u,int v){ for(;tp[u]!=tp[v];){ if(dep[tp[u]] > dep[tp[v]]) swap(u,v); v = fa[tp[v]]; } return dep[u] < dep[v] ? u : v; } int arr[maxn]; inline bool cmp(const int &u,const int &v){ return id[u] < id[v]; } int main(){ //freopen("1.in","r",stdin); // freopen("1.out","w",stdout); int T; for(scanf("%d",&T);T--;){ memset(info,0,sizeof info),cnt_e=0; scanf("%d%d",&n,&m),cnt_p=n; for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); Node(u,v),Node(v,u); } memset(dfn,0,sizeof dfn); dfs(1),R--,dfs1(1,0),tp[1]=1,dfs2(1,0); int q;scanf("%d",&q); for(;q--;){ int pt;scanf("%d",&pt); for(int i=1;i<=pt;i++) scanf("%d",&arr[i]); sort(arr+1,arr+1+pt,cmp); int ans = 0; for(int i=1;i<=pt;i++) ans += sum[arr[i]] + sum[arr[i%pt+1]] - 2 * sum[Lca(arr[i],arr[i%pt+1])]; ans /= 2; if(Lca(arr[1],arr[pt]) <= n) ans ++; ans -= pt; printf("%d\n",ans); } for(int i=1;i<=cnt_p;i++) G[i].clear(); cnt = tot = 0; } }