0%

Project2585[ZJOI2006]三色二叉树工作报告

摘要:暴力树形DP

P2585 [ZJOI2006]三色二叉树

题面

题目分析

先用一个递归输入树.

设计状态$f_{i,1/2/3}$,表示子树以i为根,被染成红色/绿色/蓝色时的最大值,最小值同理.

根据i节点的儿子数量进行转移.

代码

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
62
63
64
65
66
67
#include "chtholly.h"
#define lxl long long
#define R register
#define INF 2147483647
#define debug(x) printf("debug:%lld\n",x)
using namespace std;
const lxl maxn=500010;
lxl cnt=1,ESize;
lxl head[maxn],f[maxn][4],g[maxn][4],size[maxn];
char c;
struct _Edge
{
lxl to,next;
}e[maxn<<1];
inline lxl read() {char c=getchar(); lxl f=1,x=0; for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1); for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48); return f*x; }
inline void EdgeAdd(lxl from,lxl to) {e[ESize].to=to; e[ESize].next=head[from]; head[from]=ESize++; }
void prework(lxl now,lxl ch)
{
size[now]=ch;
char c_;
for(R lxl i=1;i<=ch;++i)
{
cin>>c_;
EdgeAdd(now,++cnt);
prework(cnt,c_-'0');
}
}
void dfs(lxl from)
{
if(size[from]==0)
{
f[from][1]=0,g[from][1]=0;
f[from][2]=0,g[from][2]=0;
f[from][3]=1,g[from][3]=1;
}
if(size[from]==1)
{
lxl to=e[head[from]].to;
dfs(to);
f[from][1]=max(f[to][2],f[to][3]);
f[from][2]=max(f[to][1],f[to][3]);
f[from][3]=max(f[to][1],f[to][2])+1;
g[from][1]=min(g[to][2],g[to][3]);
g[from][2]=min(g[to][1],g[to][3]);
g[from][3]=min(g[to][1],g[to][2])+1;
}
if(size[from]==2)
{
lxl to1=e[head[from]].to,to2=e[e[head[from]].next].to;
dfs(to1),dfs(to2);
f[from][1]=max(f[to1][2]+f[to2][3],f[to1][3]+f[to2][2]);
f[from][2]=max(f[to1][1]+f[to2][3],f[to1][3]+f[to2][1]);
f[from][3]=max(f[to1][1]+f[to2][2],f[to1][2]+f[to2][1])+1;
g[from][1]=min(g[to1][2]+g[to2][3],g[to1][3]+g[to2][2]);
g[from][2]=min(g[to1][1]+g[to2][3],g[to1][3]+g[to2][1]);
g[from][3]=min(g[to1][1]+g[to2][2],g[to1][2]+g[to2][1])+1;
}
}
int main(void)
{
memset(head,-1,sizeof(head)),memset(g,0x3f,sizeof(g));
cin>>c;
prework(1,c-'0');
dfs(1);
printf("%lld %lld\n",max(f[1][1],max(f[1][2],f[1][3])),min(g[1][1],min(g[1][2],g[1][3])));
return 0;
}