「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$的最大值。

---

代码

#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;
}