首页 > 代码库 > bzoj 4871: [Shoi2017]摧毁“树状图”
bzoj 4871: [Shoi2017]摧毁“树状图”
4871: [Shoi2017]摧毁“树状图”
Time Limit: 25 Sec Memory Limit: 512 MBSubmit: 53 Solved: 9
[Submit][Status][Discuss]
Description
自从上次神刀手帮助蚯蚓国增添了上千万人口（蚯口？），蚯蚓国发展得越来越繁荣了！最近，他们在地下发现了
一些神奇的纸张，经过仔细研究，居然是D国X市的超级计算机设计图纸！这台计算机叫做‘树状图’，由n个计算
节点与n1条可以双向通信的网线连接而成，所有计算节点用不超过n的正整数编号。顾名思义，这形成了一棵树的
结构。蚯蚓国王已在图纸上掌握了这棵树的完整信息，包括n的值与n1条网线的连接信息。于是蚯蚓国王决定，派
出蚯蚓国最强大的两个黑客，小P和小H，入侵‘‘树状图’’，尽可能地摧毁它。小P和小H精通世界上最好的编程
语言，经过一番商量后，他们决定依次采取如下的步骤：小P选择某个计算节点，作为他入侵的起始点，并在该节
点上添加一个P标记。重复以下操作若干次（可以是0次）：–小P从他当前所在的计算节点出发，选择一条没有被
标记过的网线，入侵到该网线的另一端的计算节点，并在路过的网线与目的计算节点上均添加一个P标记。小H选择
某个计算节点，作为她入侵的起始点，并在该节点上添加一个H标记。重复以下操作若干次（可以是0次）：–小H
从她当前所在的计算节点出发，选择一条没有被标记过的网线，入侵到该网线的另一端的计算节点，并在路过的网
线与目的计算节点上均添加一个H标记。（注意，小H不能经过带有P标记的网线，但是可以经过带有P标记的计算节
点）删除所有被标记过的计算节点和网线。对于剩下的每条网线，如果其一端或两端的计算节点在上一步被删除了
，则也删除这条网线。经过以上操作后，‘‘树状图’’会被断开，剩下若干个（可能是0个）连通块。为了达到
摧毁的目的，蚯蚓国王希望，连通块的个数越多越好。于是他找到了你，希望你能帮他计算这个最多的个数。小P
和小H非常心急，在你计算方案之前，他们可能就已经算好了最优方案或最优方案的一部分。你能得到一个值x：若
x=0，则说明小P和小H没有算好最优方案，你需要确定他们两个的入侵路线。若x=1，则说明小P已经算好了某种两
人合作的最优方案中，他的入侵路线。他将选择初始点p0，并沿着网线一路入侵到了目标点p1，并且他不会再沿着
网线入侵；你只需要确定小H的入侵路线。若x=2，则说明小P和小H算好了一种两人合作的最优方案，小P从点p0入
侵到了p1并停下，小H从点h0入侵到了h1并停下。此时你不需要指挥他们入侵了，只需要计算最后两步删除计算节
点与网线后，剩下的连通块个数即可。
Input
每个输入文件包含多个输入数据。输入文件的第一行为两个整数 T 和 x， T 表示
该文件包含的输入数据个数， x 的含义见上述。（同一个输入文件的所有数据的 x 都是相同的）
接下来依次输入每个数据。
每个数据的第一行有若干个整数：
若 x = 0，则该行只有一个整数 n。
若 x = 1，则该行依次有三个整数 n, p0, p1。
若 x = 2，则该行依次有五个整数 n, p0, p1, h0, h1。
保证 p0, p1, h0, h1 均为不超过 n 的正整数。
每个数据接下来有 n 1 行，每行有两个不超过 n 的正整数，表示这两个编号的计
算节点之间有一条网线将其相连。保证输入的是一棵树。
同一行相邻的整数之间用恰好一个空格隔开。
对于整数 k，设 ∑ n^k 为某个输入文件中，其 T 个输入数据的 n^k 之和。
所有输入文件满足 T ≤ 10^5, ∑ n^1 ≤ 5 × 10^5。
数据文件可能较大，请避免使用过慢的输入输出方法。
Output
对于每个数据，输出一行，表示在给定条件下，剩下连通块的最大个数。
在bzoj上听说标程T掉了，那我就无耻的骗一波访问量啦>_<
不妨把树上一条从上往下的路径看成一条线，那么每个点总共只有7种状态(值都为能形成最多的联通块个数),路径就指题面中的那两条路径
1.子树中没有任何路径 不用记录
2.子树中有一条路径，且不经过这个点 记为$f$
3.子树中有两条路径，且不经过这个点 记为$g$
4.这个点连着一个线头(经过这个点)，且子树里只有一条路径 记为$h$
5.这个点连着两个线头，且子树里只有一条路径 记为$h1$
6.这个点连着一个或三个线头，且子树里有两条路径 记为$l$
7.这个点连着两个或四个线头，且子树里有两条路径 记为$l1$
其实67中的1.3 2.4 没有什么区别，重点只是能不能再伸出去一条线
转移太麻烦了概括的说一下
显然两个能伸出去的线头是可以合并的(编号大的状态可以由编号小的状态合并而来)
这个点的线头也可以由它某个儿子直接伸过来
我记录了一个num表示当前儿子节点之前有多少个儿子节点(即全选1状态)
mk表示在之前的儿子节点某一个选2或4或5，其他全选1的最大值。
然后就是细节 。。。细节。。。(不枉我省选调了4个小时)
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define N 100005using namespace std;int read(){ int p=0;char c=getchar(); while(c<‘0‘||c>‘9‘)c=getchar(); while(c>=‘0‘&&c<=‘9‘)p=p*10+c-‘0‘,c=getchar(); return p;}int cas,t,n;int head[N],nxt[N*2],ver[N*2],tot;void add(int a,int b){ tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;}int f[N],h[N],l[N],g[N],h1[N],l1[N];int ans;int mx(int a,int b){ if(a>b)return a; return b;}void dfs(int x,int ff){ int num=0,mk=0; for(int i=head[x];i;i=nxt[i]) { if(ver[i]==ff)continue; dfs(ver[i],x); int tf=f[x],tg=g[x],th=h[x]+1,tl=l[x]+1,th1=h1[x]+1,tl1=l1[x]+1; tf=mx(tf,f[ver[i]]); tf=mx(tf,mx(h1[ver[i]],h[ver[i]])+1); tg=mx(tg,g[ver[i]]); tg=mx(tg,mx(l1[ver[i]],l[ver[i]])+1); tg=mx(tg,f[x]+mx(h1[ver[i]],h[ver[i]])); th=mx(th,h[ver[i]]+num); tl=mx(tl,l[ver[i]]+num); th1=mx(th1,h[x]+h[ver[i]]); tl=mx(tl,h[x]+f[ver[i]]); tl=mx(tl,h1[x]+h[ver[i]]); tl=mx(tl,h1[ver[i]]+h[x]); tl=mx(tl,h[ver[i]]+mk); tl1=mx(tl1,h1[ver[i]]+h1[x]); tl1=mx(tl1,l[x]+h[ver[i]]); tl1=mx(tl1,l[ver[i]]+h[x]); tl1=mx(tl1,h1[x]+f[ver[i]]); tl1=mx(tl1,h[ver[i]]+l[x]); mk=max(mk+1,num+mx(h1[ver[i]],mx(h[ver[i]],f[ver[i]]))); num++; f[x]=tf;g[x]=tg;h[x]=th;l[x]=tl;l1[x]=tl1;h1[x]=th1; } h[x]=max(h[x],num); return ;}int main(){ cas=read();t=read(); int t1,t2,t3,t4; while(cas--) { if(!t)n=read(); else if(t==1)n=read(),t1=read(),t2=read(); else n=read(),t1=read(),t2=read(),t3=read(),t4=read(); for(int i=1;i<n;i++) { t1=read();t2=read(); add(t1,t2);add(t2,t1); } dfs(1,-1); printf("%d\n",mx(g[1],mx(l1[1],l[1]))); tot=0; for(int i=1;i<=n;i++)head[i]=0; for(int i=1;i<=n;i++)h[i]=f[i]=l[i]=g[i]=l1[i]=h1[i]=0; } return 0;}
bzoj 4871: [Shoi2017]摧毁“树状图”
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。