題目：https://www.luogu.org/problemnew/show/P2585

可以把不是綠色的記成一種。仔細一想不會有沖突。如果自己是綠色，孩子的不同顏色不會沖突；如果自己不是綠色，自己的不是綠色的孩子對于自己就像二分圖一樣的感覺，所以總有方案使得不區分另外兩種顏色也不會有沖突。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5e5+5; int n,rt,tot,ls[N],rs[N],dp[N][2][2],p0;//是/否綠 最大/小 char ch[N]; void build(int &cr,int dep) {cr=++tot;if(ch[p0]=='0')p0++;else if(ch[p0]=='1')p0++,build(ls[cr],dep+1);elsep0++,build(ls[cr],dep+1),build(rs[cr],dep+1); } void dfs(int cr) {if(!ls[cr]){dp[cr][0][0]=dp[cr][0][1]=1;dp[cr][1][0]=dp[cr][1][1]=0;return;}else if(!rs[cr]){int v=ls[cr]; dfs(v);dp[cr][0][0]=dp[v][1][0]+1;dp[cr][0][1]=dp[v][1][1]+1;dp[cr][1][0]=max(dp[v][0][0],dp[v][1][0]);dp[cr][1][1]=min(dp[v][0][1],dp[v][1][1]);}else{int Ls=ls[cr],Rs=rs[cr];dfs(Ls); dfs(Rs);dp[cr][0][0]=dp[Ls][1][0]+dp[Rs][1][0]+1;dp[cr][0][1]=dp[Ls][1][1]+dp[Rs][1][1]+1;dp[cr][1][0]=max(dp[Ls][0][0]+dp[Rs][1][0],dp[Ls][1][0]+dp[Rs][0][0]);dp[cr][1][1]=min(dp[Ls][0][1]+dp[Rs][1][1],dp[Ls][1][1]+dp[Rs][0][1]);} } int main() {//freopen("TRO.IN","r",stdin);//freopen("TRO.OUT","w",stdout);scanf("%s",ch);n=strlen(ch);build(rt,1);dfs(rt);printf("%d %d\n",max(dp[rt][0][0],dp[rt][1][0]),min(dp[rt][0][1],dp[rt][1][1]));return 0; }

?

轉載于:https://www.cnblogs.com/Narh/p/9676480.html

總結

以上是生活随笔為你收集整理的洛谷 2585 [ZJOI2006]三色二叉树——树形dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。