隐藏
「SHOI2017」摧毁“树状图” - 树形动规+压缩形状 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SHOI2017」摧毁“树状图” - 树形动规+压缩形状

题目大意

    在树上去掉两条链,使得剩下的连通块个数最多。


题目分析

显然这是一道树形动规,可以把状态压进去。
一眼秒掉,然后开始写。
然后3个小时就过去了,过不了大样例。

参考SD_le的状态:
设$f(i,1\sim6)$分别表示:

  1. 子树中有一条不与根相连的链
  2. 子树中有两条不与根相连的链
  3. 子树中有一条与根相连的链
  4. 子树中有两条与根相连的链
  5. 子树中有三条与根相连的链,或一条与根相连的链+一条不与根相连的链
  6. 子树中有四条与根相连的链,或两条与根相连的链+一条不与根相连的链

然后就可以开始复杂的转移了,设$x$是当前结点,$y$是子结点,使用$x_i$表示$f(x,i)$。为了方便转移,我们按顺序一个一个考虑儿子,只考虑到当前的子结点,不考虑当前儿子之后的子结点,$d$是到当前的儿子结点个数。
以下是转移:

  1. $y_1$,$y_3+1$,$y_4+1$
  2. $y_2$,$x_1+y_1-1$,$y_5+1$,$y_6+1$,$x_1+y_3$,$x_1+y_4$
  3. $x_3+1$,$y_3+d$,$d+1$(新断点)
  4. $x_4+1$,$x_3+y_3$
  5. $x_5+1$,$y_5+d$,$x_3+y_1$,$x_1+y_3$(标记1),$x_3+y_4$,$x_4+y_3$
  6. $x_6+1$,$x_4+y_4$,$x_5+y_3$,$x_3+y_5$,$x_4+y_1$

注意标记1的转移比较特殊,因为用到了$x_1$的转移,而$x_1$在转移时有$y_3+1,y_4+1$,算了根的连通块,而在转移$5$时不应该有,因此需要新开一个变量记录$\max(y_1,y_3,y_4)+d$的最大值。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=100005;

vector<int> edges[maxn];
int n,x,f[maxn][7];

void TreeDp(int Now,int fa) {
int num=0,x1=INT_MIN/2;
for(int Next:edges[Now]) {
if(Next==fa)continue;
TreeDp(Next,Now);
int last[7];
copy(f[Now],f[Now]+7,last);
f[Now][1]=max({f[Now][1],f[Next][1],f[Next][3]+1,f[Next][4]+1});
f[Now][2]=max({f[Now][2],f[Next][2],last[1]+f[Next][1]-1,f[Next][5]+1,f[Next][6]+1,last[1]+f[Next][3],last[1]+f[Next][4]});
f[Now][3]=max(f[Now][3]+1,f[Next][3]+num);
f[Now][4]=max(f[Now][4]+1,last[3]+f[Next][3]);
f[Now][5]=max({f[Now][5]+1,f[Next][5]+num,last[3]+f[Next][1],last[4]+f[Next][3],last[3]+f[Next][4],x1+f[Next][3]});
f[Now][6]=max({f[Now][6]+1,last[4]+f[Next][4],last[5]+f[Next][3],last[3]+f[Next][5],last[4]+f[Next][1]});
x1=max(x1+1,num+max({f[Next][1],f[Next][3],f[Next][4]}));
num++;
}
f[Now][3]=max(f[Now][3],num);
}

void Clear() {
for(int i=1; i<=n; i++) {
edges[i].clear();
fill(f[i],f[i]+7,0);
}
}

int main() {
int t=Get_Int();
x=Get_Int();
while(t--) {
Clear();
n=Get_Int();
if(x==1)Get_Int(),Get_Int();
if(x==2)Get_Int(),Get_Int(),Get_Int(),Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
edges[x].push_back(y);
edges[y].push_back(x);
}
TreeDp(1,0);
printf("%d\n",max({f[1][2],f[1][5],f[1][6]}));
}
return 0;
}
姥爷们赏瓶冰阔落吧~