首页 > 代码库 > bzoj 4871: [Shoi2017]摧毁“树状图”

bzoj 4871: [Shoi2017]摧毁“树状图”

 

4871: [Shoi2017]摧毁“树状图”

Time Limit: 25 Sec  Memory Limit: 512 MB
Submit: 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]摧毁“树状图”