【ybtoj高效进阶 21169】毁灭计划(分类讨论)(树形DP)
毁灭计划
题目链接:ybtoj高效进阶 21169
题目大意
给你一棵树,然后你要找两条无相交边的路径,使得删去这两个路径的点和它相邻的边之后,这个树被分成尽可能多的连通块。
思路
这题就是阴间的分类讨论 DP。
(题解十几页是真的**)
首先是设 f i , j f_{i,j} fi,j 是 i i i 的子树内,当前形态是 j j j 的最大连通块数。
然后介绍形态:
0
0
0:一个端点在当前根
i
i
i,另一个在子树内。
1
1
1:不经过
i
i
i,在
i
i
i 子树内一条链。
2
2
2:在
i
i
i 子树内一条链,经过
i
i
i 点。
3
3
3:这个是选两条链,一条是类型
0
0
0 的一条是类型
1
1
1 的。
然后接着我们考虑两个问题:
如何统计答案?如何转移
f
f
f 数组。
继续分类讨论,首先考虑解决统计答案。
统计答案一共六种情况。
(后面的 − [ u = = 1 ] -[u==1] −[u==1] 是因为如果不是最根上面就有东西就有一个连通块,如果是跟上面的就没有连通块所以少了一个)
第一种:
f
u
,
0
+
f
v
,
3
−
[
u
=
=
1
]
f_{u,0}+f_{v,3}-[u==1]
fu,0+fv,3−[u==1]
第二种:
f
u
,
0
+
f
v
,
3
−
[
u
=
=
1
]
f_{u,0}+f_{v,3}-[u==1]
fu,0+fv,3−[u==1]
第三种:
f
u
,
1
+
f
v
,
2
f_{u,1}+f_{v,2}
fu,1+fv,2
第四种:
f
u
,
1
+
f
v
,
1
−
1
f_{u,1}+f_{v,1}-1
fu,1+fv,1−1(这个减一是上面连一起了少了一个)
第五种:
f
u
,
2
+
f
v
,
1
−
[
u
=
=
1
]
f_{u,2}+f_{v,1}-[u==1]
fu,2+fv,1−[u==1]
第六种:
f
u
,
2
+
f
v
,
2
−
[
u
=
=
1
]
f_{u,2}+f_{v,2}-[u==1]
fu,2+fv,2−[u==1]
接着考虑转移。(这里设 d e g i deg_i degi 为 i i i 的儿子数)
0
0
0:
只有一种方法,在儿子的路径上延伸多
i
i
i 这个儿子。
f
v
,
0
+
d
e
g
p
−
1
f_{v,0}+deg_p-1
fv,0+degp−1
1
1
1:
方法一:
f
v
,
1
f_{v,1}
fv,1
方法二:
f
v
,
2
+
1
f_{v,2}+1
fv,2+1
2
2
2:
一种方法,
f
u
,
0
+
f
v
,
0
−
1
f_{u,0}+f_{v,0}-1
fu,0+fv,0−1
3
3
3:
方法一:
f
u
,
0
+
f
v
,
2
−
1
f_{u,0}+f_{v,2}-1
fu,0+fv,2−1
方法二:
f
u
,
0
+
f
v
,
1
−
1
f_{u,0}+f_{v,1}-1
fu,0+fv,1−1
方法三:
f
u
,
2
+
f
v
,
0
−
1
f_{u,2}+f_{v,0}-1
fu,2+fv,0−1
方法四:
f
v
,
3
+
d
e
g
u
−
1
f_{v,3}+deg_u-1
fv,3+degu−1
方法五:
f
v
,
0
+
d
e
g
u
+
m
a
x
n
−
2
f_{v,0}+deg_u+maxn-2
fv,0+degu+maxn−2(
m
a
x
n
maxn
maxn 是之前遍历过的
v
v
v 中最大的
f
v
,
1
,
f
v
,
2
f_{v,1},f_{v,2}
fv,1,fv,2)
然后注意的是枚举的顺序,统计答案放在最前面,然后
3
3
3 的要在
0
,
2
0,2
0,2 之前,
2
2
2 要在
0
0
0 之间。
(因为用到了,不能用修改之后的,要用修改之前的)
代码
#include<cstdio>
#include<iostream>
using namespace std;
struct node {
int to, nxt;
}e[1000005];
int T, X, n, x, y;
int le[500005], KK;
int deg[500005], ans;
int f[500005][5];
void csh() {
KK = 0; ans = 0;
for (int i = 1; i <= n; i++) le[i] = 0, deg[i] = 0;
}
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
e[++KK] = (node){x, le[y]}; le[y] = KK;
}
void DP(int now, int father) {
f[now][0] = f[now][2] = f[now][3] = deg[now];
f[now][1] = 1;
int maxn = 0;
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father) {
DP(e[i].to, now);
ans = max(ans, f[now][3] + f[e[i].to][0] - (now == 1));
ans = max(ans, f[now][0] + f[e[i].to][3] - (now == 1));
ans = max(ans, f[now][1] + f[e[i].to][2]);
ans = max(ans, f[now][1] + f[e[i].to][1] - 1);
ans = max(ans, f[now][2] + f[e[i].to][1] - (now == 1));
ans = max(ans, f[now][2] + f[e[i].to][2] - (now == 1));
f[now][1] = max(f[now][1], f[e[i].to][1]);
f[now][1] = max(f[now][1], f[e[i].to][2] + 1);
f[now][3] = max(f[now][3], f[now][0] + f[e[i].to][2] - 1);
f[now][3] = max(f[now][3], f[now][0] + f[e[i].to][1] - 1);
f[now][3] = max(f[now][3], f[now][2] + f[e[i].to][0] - 1);
f[now][3] = max(f[now][3], f[e[i].to][3] + deg[now] - 1);
f[now][3] = max(f[now][3], f[e[i].to][0] + deg[now] + maxn - 2);
f[now][2] = max(f[now][2], f[now][0] + f[e[i].to][0] - 1);
f[now][0] = max(f[now][0], f[e[i].to][0] + deg[now] - 1);
maxn = max(maxn, max(f[e[i].to][1], f[e[i].to][2]));
}
}
int main() {
// freopen("destroy.in", "r", stdin);
// freopen("destroy.out", "w",stdout);
scanf("%d %d", &T, &X);
while (T--) {
scanf("%d", &n);
if (X >= 1) scanf("%d %d", &x, &y);
if (X >= 2) scanf("%d %d", &x, &y);
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
add(x, y);
deg[x]++; deg[y]++;
}
for (int i = 2; i <= n; i++) deg[i]--;
DP(1, 0);
printf("%d\n", ans);
csh();
}
return 0;
}