c/c++语言开发共享洛谷：P2585 [ZJOI2006]三色二叉树（树dp，提高+/省选-）

题目：

分析：我总觉得紫书上见过类似的。最多的应该考虑四层。

自己的想法太复杂：如最少的自己的想法是，首先明确只有这种情况才要染绿色。

如果是有两个子节点，三种情况，父，两子分别为绿色。

父为绿。则判断子的子。

子为绿，则该子的 子的子，兄弟的子。

妈耶，一直想着非绿色的两种颜色统一化，结果就是这么简单：不过我充分利用非绿色两种颜色统一化比题解时间应该少一半：

代码：

#include<bits/stdc++.h> using namespace std; string s; vector<vector<int> > vv; int f_tree(int &x) {//初始化树。   if(s[x]=='0')  {   return x;  }  if(s[x]=='2'){   int c=x;   x++;   vv[c].push_back(f_tree(x));   x++;   vv[c].push_back(f_tree(x));   return c;  }  if(s[x]=='1'){   int c=x;   x++;   vv[c].push_back(f_tree(x));   return c;  } } long long A1[500005][3]; long long A2[500005][3]; long long f1(int x,int y) {  if(A1[x][y]!=-1) return A1[x][y];  if(y==0)  {   if(vv[x].size()==0)   {    A1[x][y]=1;    return A1[x][y];    }   if(vv[x].size()==1)   {    A1[x][y]=f1(vv[x][0],1)+1;    A1[vv[x][0]][2]=A1[vv[x][0]][1];    return A1[x][y];    }   if(vv[x].size()==2)   {    A1[x][y]=f1(vv[x][0],1)+f1(vv[x][1],1)+1;    A1[vv[x][0]][2]=A1[vv[x][0]][1];    A1[vv[x][1]][2]=A1[vv[x][1]][1];    return A1[x][y];    }  }  if(y==1)  {   if(vv[x].size()==0)   {    A1[x][y]=0;    A1[x][2]=A1[x][y];    return A1[x][y];    }   if(vv[x].size()==1)   {    A1[x][y]=max(f1(vv[x][0],2),f1(vv[x][0],0));    A1[vv[x][0]][1]=A1[vv[x][0]][2];    return A1[x][y];    }   if(vv[x].size()==2)   {    A1[x][y]=max(f1(vv[x][0],0)+f1(vv[x][1],2),f1(vv[x][0],2)+f1(vv[x][1],0));    A1[vv[x][0]][1]=A1[vv[x][0]][2];    A1[vv[x][1]][1]=A1[vv[x][1]][2];    return A1[x][y];    }  }  if(y==2)  {   if(vv[x].size()==0)   {    A1[x][y]=0;    A1[x][1]=A1[x][y];    return A1[x][y];    }   if(vv[x].size()==1)   {    A1[x][y]=max(f1(vv[x][0],1),f1(vv[x][0],0));    A1[vv[x][0]][2]=A1[vv[x][0]][1];    return A1[x][y];    }   if(vv[x].size()==2)   {    A1[x][y]=max(f1(vv[x][0],0)+f1(vv[x][1],1),f1(vv[x][0],1)+f1(vv[x][1],0));    A1[vv[x][0]][2]=A1[vv[x][0]][1];    A1[vv[x][1]][2]=A1[vv[x][1]][1];    return A1[x][y];   }  } } long long f2(int x,int y) {  if(A1[x][y]!=-1) return A1[x][y];  A1[x][y]=1<<30;  if(y==0)  {   if(vv[x].size()==0)   {    A1[x][y]=1;    return A1[x][y];    }   if(vv[x].size()==1)   {    A1[x][y]=f2(vv[x][0],1)+1;    A1[vv[x][0]][2]=A1[vv[x][0]][1];    return A1[x][y];    }   if(vv[x].size()==2)   {    A1[x][y]=f2(vv[x][0],1)+f2(vv[x][1],1)+1;    A1[vv[x][0]][2]=A1[vv[x][0]][1];    A1[vv[x][1]][2]=A1[vv[x][1]][1];    return A1[x][y];    }  }  if(y==1)  {   if(vv[x].size()==0)   {    A1[x][y]=0;    A1[x][2]=A1[x][y];    return A1[x][y];    }   if(vv[x].size()==1)   {    A1[x][y]=min(f2(vv[x][0],2),f2(vv[x][0],0));    A1[vv[x][0]][1]=A1[vv[x][0]][2];    return A1[x][y];    }   if(vv[x].size()==2)   {    A1[x][y]=min(f2(vv[x][0],0)+f2(vv[x][1],2),f2(vv[x][0],2)+f2(vv[x][1],0));    A1[vv[x][0]][1]=A1[vv[x][0]][2];    A1[vv[x][1]][1]=A1[vv[x][1]][2];    return A1[x][y];   }  }  if(y==2)  {   if(vv[x].size()==0)   {    A1[x][y]=0;    A1[x][1]=A1[x][y];    return A1[x][y];    }   if(vv[x].size()==1)   {    A1[x][y]=min(f2(vv[x][0],1),f2(vv[x][0],0));    A1[vv[x][0]][2]=A1[vv[x][0]][1];    return A1[x][y];    }   if(vv[x].size()==2)   {    A1[x][y]=min(f2(vv[x][0],0)+f2(vv[x][1],1),f2(vv[x][0],1)+f2(vv[x][1],0));    A1[vv[x][0]][2]=A1[vv[x][0]][1];    A1[vv[x][1]][2]=A1[vv[x][1]][1];    return A1[x][y];   }  } } int main() {  cin>>s;  vector<int> v;  for(int i=0;i<s.size();i++) vv.push_back(v);  memset(A1,-1,sizeof(A1));  int c=0;  f_tree(c);  cout<<max(f1(0,0),f1(0,1))<<' ';  memset(A1,-1,sizeof(A1));  cout<<min(f2(0,0),f2(0,1)); } 

c/c++开发分享洛谷：P2585 [ZJOI2006]三色二叉树（树dp，提高+/省选-）地址：https://blog.csdn.net/weixin_42721412/article/details/107597262