1864: [Zjoi2006]三色二叉树
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 1118 Solved: 818
[Submit][Status][Discuss]
Description
Input
仅有一行，不超过500000个字符，表示一个二叉树序列。
Output
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2
HINT
Source
哇呀呀呀呀呀这么简单的树形dp竟然没想到 啊啊啊啊啊laj好菜哇
f[x][1]表示当前点涂绿他和他的子树中涂绿的个数 f[x][0]表示当前点非绿他和他的子树中涂绿的个数
然后……乱搞搞就行咯 _(:зゝ∠)_
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=3e5+5; 5 int n,ans1,ans2,l[MAX],r[MAX],f[MAX][2]; 6 void scan(int x){ 7 char c=getchar(); 8 if (c=='0') return; 9 ++n;l[x]=n; scan(n); 10 if (c=='2') ++n,r[x]=n,scan(n); 11 } 12 void dfs1(int x){ 13 if (!x) return; 14 dfs1(l[x]),dfs1(r[x]); 15 f[x][1]=f[l[x]][0]+f[r[x]][0]+1; 16 f[x][0]=max(f[l[x]][0]+f[r[x]][1],f[l[x]][1]+f[r[x]][0]); 17 } 18 void dfs2(int x){ 19 if (!x) return; 20 dfs2(l[x]),dfs2(r[x]); 21 f[x][1]=f[l[x]][0]+f[r[x]][0]+1; 22 f[x][0]=min(f[l[x]][0]+f[r[x]][1],f[l[x]][1]+f[r[x]][0]); 23 } 24 int main(){ 25 freopen ("tree.in","r",stdin);freopen ("tree.out","w",stdout); 26 int i,j;n=1; 27 scan(1); 28 dfs1(1);ans1=max(f[1][0],f[1][1]); 29 memset(f,0,sizeof(f)); 30 dfs2(1);ans2=min(f[1][0],f[1][1]); 31 printf("%d %d",ans1,ans2); 32 return 0; 33 }