当前位置: 首页 > news >正文

NKOJ全TJ计划——NP11745

题目内容

最小割板子

小 E 有一棵有\(n\) 个点的无根树,它的节点编号为\(1\)\(n\) ,其中第\(i(i\in [1,n-1])\) 条边连接节点\(u_i\)\(v_i\) 。同时他还有\(m\)条树上的路径,第\(i\)条路径为从节点\(a_i\)\(b_i\)的路径 (请注意,可能存在\(a_i=b_i\) 的情况,此时路径退化为一个点)。

但是小 T 并不喜欢这些路径,所以他想对这棵树进行一些破坏从而破坏路径。具体来说,小 T 可以做以下操作任意多次:

选择一个仍然存在的节点,并同时删除这个节点以及与之相连的边(即边的其中一个节点为删除的节点)。

小 T 认为,在经过一系列的破坏后,一条初始的连接节点\(a_i\)\(b_i\) 的路径被成功破坏当且仅当以下条件成立:

节点\(a_i\)\(b_i\) 中至少一个点已经被删除;或者节点\(a_i\)\(b_i\) 都存在,但此时已经不连通。

但是小 T 做破坏需要花费时间,而他还忙着去打乒乓球,所以他想知道他最少做多少次破坏操作才能使得\(m\) 条路径都被破坏。同时,他不希望你只给个答案,所以小 T 要求你构造方案。
\(3\le n\le 2\times 10^5,2\le m\le 2\times 10^5\)

解题思路

前置知识:DFS序、线段树、ST表、LCA。

我们可以很轻松地想到将删去的点点权设为1,而如果某个\(a_i\)\(b_i\)的路径上点权和大于1,就跳过这一对。

显然,这可以用DFS序,而因为当年上DFS序的时候,是一个阳光明媚的下午,令人昏昏欲睡,而旁边同学精彩的游戏技术又令人忍不住想看看,于是全班都没听课。

所以,我是今天新自学的DFS序。

显然,这是DFS序中的“点改链查”,我们可以用树状数组来实现。

这里顺便说一句,DFS序搭配ST表可以实现LCA,请自行查询资料。

但是每一次我们删除那个点呢?我们可以删除经过最多的点(吗?)。实际上,这是很容易被Hack的,我们可以把\(a_i,b_i\)一起按照\(deep[LCA(a_i,b_i)]\)从大到小排序,每次删除\(LCA(a_i,b_i)\)

那样,就可以愉快的码字了。

代码

#include<bits/stdc++.h>
using namespace std;
#define N 200004
int in[N],out[N],ch[N*2],st[N][20],lg[N],dfn[N],b[N*2],doit[N],death[N],fu[N];
int n,m,i,j,x,y,t,s,t2;
struct it{int q,w;
}a[N];
vector<int> v[N],u[N];
int sr(int x,int y){if(dfn[x]>dfn[y]) return y;return x;
}
int l(int x){return x&(-x);
}
void add(int a,int x){int go=a;while(go<=2*n){b[go]+=x;go+=l(go);}return ;
}
int sum(int a){int go=a,s=0;while(go){s+=b[go];go-=l(go);}return s;
}
void dfs(int x,int fa){in[x]=++t;dfn[x]=++t2;st[dfn[x]][0]=fa;death[x]=death[fa]+1;fu[x]=fa;for(int i=0;i<v[x].size();i++){if(v[x][i]==fa) continue;u[x].push_back(v[x][i]);dfs(v[x][i],x);}out[x]=++t;return ;
}
int lca(int x1,int y1){int x=x1,y=y1;if(x==y) return x;x=dfn[x];y=dfn[y];if(x>y) swap(x,y);t=lg[y-x];return sr(st[y-(1<<t)+1][t],st[x+1][t]);
}
bool cmp(it e,it r){return death[lca(e.w,e.q)]>death[lca(r.w,r.q)];
}
int main()
{cin>>n>>m;for(i=1;i<n;i++){scanf("%d%d",&x,&y);v[x].push_back(y);v[y].push_back(x);}dfs(1,0);for(i=2;i<=n;i++) lg[i]=lg[i/2]+1;for(i=1;i<=lg[n];i++){for(j=1;j<=n+1-(1<<i);j++){st[j][i]=sr(st[j][i-1],st[j+(1<<i-1)][i-1]);}}for(i=1;i<=n;i++) ch[in[i]]=ch[out[i]]=i;/*for(i=1;i<=n;i++) cout<<in[i]<<" ";cout<<"\n";for(i=1;i<=n;i++) cout<<out[i]<<" ";cout<<"\n";*/for(i=1;i<=m;i++){scanf("%d%d",&a[i].q,&a[i].w);}sort(a+1,a+1+m,cmp);
//	cout<<"\n";for(i=1;i<=m;i++){x=a[i].q;y=a[i].w;
//		cout<<x<<" "<<y<<" "<<lca(x,y)<<" "<<in[lca(x,y)]<<" "<<out[lca(x,y)]<<"\n";if(sum(in[y])+sum(in[x])-sum(in[lca(x,y)])-sum(in[fu[lca(x,y)]])){ continue;}add(in[lca(x,y)],1);add(out[lca(x,y)],-1);doit[++s]=lca(x,y);
//		for(j=1;j<=n*2;j++)cout<<sum(j)-sum(j-1)<<" ";
//		cout<<"\n\n";}printf("%d\n",s);sort(doit+1,doit+1+s);for(i=1;i<=s;i++) printf("%d ",doit[i]);
}
/*
10
7
1 2
2 3
3 4
1 5
1 6
5 7
4 8
6 9
3 10
2 9
7 8
5 7
1 9
7 8
7 9
3 6
if(dfn[x]>dfn[y]) swap(x,y);
if(sum(dfn[y]-dfn[x-1])){
continue;
}
add(lca(x,y),1);
doit[++s]=lca(x,y);
*/
http://www.hskmm.com/?act=detail&tid=25532

相关文章:

  • InfinityFree教程 ——免费搭建属于你的网站
  • 关于调和级数估算前n项的和
  • 10.6 模考 T4(QOJ 1836)
  • 实用指南:【Node.js 深度解析】npm install 遭遇:npm ERR! code CERT_HAS_EXPIRED 错误的终极解决方案
  • 顺序结构
  • Windows漏洞利用技巧:虚拟内存访问陷阱(2025更新)
  • Python编译期优化:隐藏在代码背后的效率魔法
  • 一篇文章带你了解 WGCLOUD运维监控系统的部署与应用
  • 选择结构
  • Python函数默认参数陷阱:可变对象的共享问题深度解析
  • 无需安装的Photoshop:网页版完整使用指南与在线图片编辑技巧
  • 求阶
  • gin 框架 - 教程
  • 赛前训练 5 树形 dp
  • 递推求解逆元
  • 一些做题记录(2025 2-3)
  • 智慧决策的透明化路径:“空白金兰契”架构下的“悟空备案制”研究
  • 笔记:寻找适合自己的简历工具(YAMLResume)
  • 实用指南:Linux 权限管理入门:从基础到实践
  • vue插槽
  • Magnet Axiom 9.6 新增功能概览 - 数字取证与分析
  • Windows 11 24H2 中文版、英文版 (x64、ARM64) 下载 (2025 年 9 月发布)
  • Windows 11 25H2 正式版发布,新增功能简介
  • 无法定时发送
  • 计算能力的重要性:从内存配置到进程迁移的未来展望
  • MongoDB财报超预期,文档数据库技术解析
  • 深入解析:【RabbitMQ】- Channel和Delivery Tag机制
  • 2020CSPS T1 儒略日题解
  • 调用百度AI接口实现网络图片中的文字识别
  • 英语_阅读_ChatGPT_待读