P4606 [SDOI2018]战略游戏:广义圆方树

其实会了圆方树就不难,达不到黑,最多算个紫

那个转换到圆方树上以后的处理方法,画画图就能看出来,所以做图论题一定要多画图,并把图画清楚点啊!!

但我怎么从9点一直调到下午4点啊啊啊啊啊

双倍经验:P4320 道路相遇,但是被卡常了并没有过

给出一个无向图,和 \(q\) 个询问,每次给出 \(s\) 个点,问存在几个点,使得这个点和他相连的边被去除后,这 \(s\) 个点中,至少存在一对点互不相通


先用 tarjan 对原图建立圆方树,然后可以枚举每两对给定的点,求他们的树上路径中,有几个非叶子节点的圆点(根据圆方树的性质,这就是他们之间的割点,也就是满足题目要求的点)

这些点的并集的大小即为答案

但这样复杂度显然过不去,而且这样描述答案不方便做转化(一开始我就是一直在这样想,导致卡了好长时间)

所以应该给出另一种对答案的描述:在圆方树中,包含所有给出的点的联通块,最小的大小,再减去 \(s\) 即为答案

显然这和刚才那样是等价的

但是还是不会算

发现题目中给出的 \(s\) 个点是排好序的,然而这并没有什么用,但这启示我们,不妨把给出的点按照他们在圆方树中的 dfs 序重新排序

然后画一个图,发现,如果由 dfs 序从小到大,以此走过所有的点,然后再从第 \(s\) 个点走回第 \(1\) 个点

在走过路径中,如果不考虑每相邻两个点的 LCA(此时我们走的是树上最短路径,显然会经过 LCA,这里说的不考虑就是不把它计入在内),每个点恰好被走了两次,而这些被走过的点恰好就是我们要求的联通块

其实这里本来是有个图的,但画的太丑就没加进来,自己画一画吧

所以我们只要为每个点赋值一个点权,方点为 \(0\) 圆点为 \(1\),倍增求树上路径点权和就好了

当然,最后还要再除以二,再减去 \(s\)

不过这样会有一个问题,就是第一个点和第 \(s\) 个点的 LCA 会不被统计,所以如果这个点是个圆点答案就再加一

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
#define N 400007
#define M 400006
struct graph{
int tot;
int fir[N],nex[M],to[M];
inline void add(int u,int v){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
}
inline void clear(){
std::memset(fir,0,sizeof fir);std::memset(to,0,sizeof to);
std::memset(nex,0,sizeof nex);tot=0;
}
}T,G;
int n,m;
int dfn[N],deep[N],size[N],dfscnt;
int fa[22][N],val[N],S[N];
inline int cmp(int x,int y){return dfn[x]<dfn[y];}
struct get_bcc{
int dfn[N],low[N],stack[N],top;
int bcccnt,dfscnt;
void tarjan(int u){
dfn[u]=low[u]=++dfscnt;stack[top++]=u;
for(reg int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(!dfn[v]){
tarjan(v);
low[u]=std::min(low[u],low[v]);
if(low[v]>=dfn[u]){
bcccnt++;
do{
T.add(bcccnt,stack[--top]);T.add(stack[top],bcccnt);
}while(stack[top]^v);
T.add(bcccnt,u);T.add(u,bcccnt);
}
}
else low[u]=std::min(low[u],dfn[v]);
}
}
}BCC;
inline void clear(){
T.clear();G.clear();
std::memset(BCC.dfn,0,sizeof BCC.dfn);std::memset(BCC.low,0,sizeof BCC.low);
BCC.top=0;BCC.dfscnt=0;
dfscnt=0;
std::memset(dfn,0,sizeof dfn);
std::memset(fa,0,sizeof fa);std::memset(val,0,sizeof val);
std::memset(deep,0,sizeof deep);std::memset(size,0,sizeof size);
}
void dfs(int u,int fat){
size[u]=1;deep[u]=deep[fat]+1;
dfn[u]=++dfscnt;fa[0][u]=fat;
val[u]=val[fat]+(u<=n);
for(reg int v,i=T.fir[u];i;i=T.nex[i]){
v=T.to[i];
if(v==fat) continue;
dfs(v,u);size[u]+=size[v];
}
}
inline void pre(){
for(reg int i=1;i<=20;i++){
for(reg int j=1;j<=BCC.bcccnt;j++) fa[i][j]=fa[i-1][fa[i-1][j]];
}
}
inline int get(int x,int y){
if(deep[x]<deep[y]) std::swap(x,y);
for(reg int i=20;~i;i--)
if(deep[fa[i][x]]>=deep[y])x=fa[i][x];
if(x==y) return x;
for(reg int i=20;~i;i--)
if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
int main(){int cases=read();while(cases--){
BCC.bcccnt=n=read();m=read();
for(reg int u,v,i=1;i<=m;i++){
u=read();v=read();
G.add(u,v);G.add(v,u);
}
BCC.tarjan(1);
dfs(1,0);
pre();
//
// EN;EN;
// std::printf("n : %d m : %d bcccnt : %d\n",n,m,BCC.bcccnt);
// for(reg int i=1;i<=BCC.bcccnt;i++){
// std::printf("now : %d size : %d deep : %d dfn : %d val : %d\n",i,size[i],deep[i],dfn[i],val[0][i]);
// for(reg int j=T.fir[i];j;j=T.nex[j]) std::printf("%d ",T.to[j]);
// EN;
// }
//
reg int s,ans,lca;
int q=read();while(q--){
s=read();ans=0;
for(reg int i=1;i<=s;i++) S[i]=read();
std::sort(S+1,S+1+s,cmp);S[s+1]=S[1];
for(reg int i=1;i<=s;i++){
lca=get(S[i],S[i+1]);
ans+=val[S[i]]+val[S[i+1]]-val[lca]*2;
}
ans>>=1;ans-=s;
ans+=(get(S[1],S[s])<=n);
std::printf("%d\n",ans);
}
if(cases) clear();
}
return 0;
}

最新文章

  1. ajax-登陆+验证码
  2. 测试Servlet生命周期学习笔记
  3. poj 2485 Highways 最小生成树
  4. springMVC spring hibernate pom.xml备份
  5. FormCreate &amp; FormActivate &amp; FormShow执行顺序演示
  6. Java和MongoDB之Hello World
  7. codeforces C. Painting Fence
  8. Android简易记事本
  9. fifteen-puzzle
  10. 在公网上的Linux,我的一些配置分享
  11. linux shell基本知识
  12. [MS] 微软官网下载安装SQLSERVER2019的rpm
  13. Python3函数式编程
  14. (Tcp协议)linux上netstat -atunlp后出现的数据的意思(socket状态)
  15. CSS-图像映射
  16. Java非静态内部类为什么不能有静态成员
  17. 命令行web客户端与HTTP REST API调试工具
  18. Discuz常见小问题-如何设置QQ邮箱注册验证
  19. Yii2.0的乐观锁与悲观锁(转)
  20. conversion vs recommendation

热门文章

  1. 彻底卸载----LoadRunner
  2. Mac配置hosts文件
  3. AJ学IOS 之微博项目实战(9)微博模型之时间相关重要操作,判断刚刚,昨天,今年等等
  4. 如何用python爬虫从爬取一章小说到爬取全站小说
  5. stand up meeting 11/18/2015
  6. C. 无穷的小数
  7. testlink数据表分析
  8. pyinstaller打包
  9. 零基础的学习者应该怎么开始学习呢?Python核心知识学习思维分享
  10. Spark SQL源码解析(二)Antlr4解析Sql并生成树