P4606 [SDOI2018]战略游戏(圆方树+思维技巧)

$这道题画个图,发现和圆方树关系很大!!$

$比如u和v在圆方树上的路径经过几个圆点,那些圆点就符合要求!!$

$解释:经过的圆点连接着两个方点,分别属于u的点双和v的点双$

$去掉这个点,u和v分割开来$

$所以现在就是求给定的s集合任意两点路径经过的圆点个数(不重复)$

但是会超时

$我们发现要求的就是s集合的最小连通子图中的圆点啊!!$

$那怎么求?$

$想象一下dfs的过程,搜索某棵子树,然后原路返回,在搜索另一颗子树...$

$也就是按照dfs序给s集合排序$

$我们只需要计算相邻两点的路径上的圆点即可!!(当然这样每条边相当于走了两次)$

$最后除以2减去s中集合的个数即可$

$s集合首位元素也要计算路径上的贡献,但是贡献是点,不好统计$

$我们把每个圆点的贡献放在它和父亲的边上去(贡献为1)$

$这样我们可以很方便的用lca来求树上两点的距离!!$

$最后,还有一个细节,如果s集合首尾元素的lca是圆点$

$那么这个点的贡献没有算进去(不在连通子图里,在外边的边了)$

$需要额外加上去$

#include <bits/stdc++.h> using namespace std; const int maxn=2e6+10; int t,n,m,f,q; vector<int>vec[maxn]; struct edge{ int to,nxt; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v){ d[++cnt]=(edge){v,head[u]},head[u]=cnt; } void ins(int u,int v){ vec[u].push_back(v); } int low[maxn],dfn[maxn],stac[maxn],iid,top; void tarjan(int u) { low[u]=dfn[u]=++iid,stac[++top]=u; for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( !dfn[v] ) { tarjan(v),low[u]=min(low[u],low[v]); if( low[v]>=dfn[u] ) { ++f;//发现割点 while( 1 ) { ins(f,stac[top]); ins(stac[top],f); if( stac[top--]==v ) break; } ins(f,u); ins(u,f); } } else low[u]=min( low[u],dfn[v] ); } } int id[maxn],fa[maxn][22],dis[maxn],num,deep[maxn],s[maxn]; void dfs(int u,int father) { id[u]=++num,deep[u]=deep[father]+1; fa[u][0]=father, dis[u]=dis[father]+( u<=n ); for(int i=1;i<=20;i++) fa[u][i]=fa[ fa[u][i-1] ][i-1]; for(int i=0;i<vec[u].size();i++) if( vec[u][i]!=father ) dfs( vec[u][i],u ); } int lca(int x,int y) { if( deep[x]<deep[y] ) swap(x,y); // for(int i=log(deep[x]);i>=0;i--) // if( deep[fa[x][i]]>=deep[y] ) x=fa[x][i]; for(int j=0,d=deep[x]-deep[y];d;j++,d>>=1) if( d&1 ) x=fa[x][j]; if( x==y ) return x; for(int i=18;i>=0;i--) if( fa[x][i]!=fa[y][i] ) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } bool com(int a,int b){ return id[a]<id[b]; } void init() { iid=0,num=0,cnt=1,top=0; for(int i=1;i<=f;i++) { vec[i].clear(),head[i]=0; dfn[i]=low[i]=0; id[i]=dis[i]=deep[i]=0; for(int j=0;j<=20;j++) fa[i][j]=0; } } int main() { ios::sync_with_stdio(false); // cin.tie(0),cout.tie(0); cin >> t; while( t-- ) { cin >> n >> m; f=n; for(int i=1;i<=m;i++) { int l,r; cin >> l >> r; add(l,r); add(r,l); } tarjan(1),top--; dfs(1,0); cin >> q; while( q-- ) { int shu,ans=0; cin >> shu; ans=-2*shu; for(int i=1;i<=shu;i++) cin >> s[i]; sort(s+1,s+1+shu,com); for(int i=1;i<shu;i++) { int u=s[i],v=s[i+1]; ans+=dis[u]+dis[v]-2*dis[lca(u,v)]; } ans+=dis[s[1]]+dis[s[shu]]-2*dis[lca(s[1],s[shu])]; if( lca(s[1],s[shu])<=n ) ans+=2; cout << ans/2 << '\n'; } init(); } }