M_sea

洛谷2585 [ZJOI2006]三色二叉树
Luogu算法DP。设$f[i][0/1]$表示以$i$为根的子树在$i$为/不为绿色时的最大绿色节点数。那么$f...
扫描右侧二维码阅读全文
27
2018/02

洛谷2585 [ZJOI2006]三色二叉树

Luogu

算法

DP。
设$f[i][0/1]$表示以$i$为根的子树在$i$为/不为绿色时的最大绿色节点数。
那么$f[i][1]=f[lson][0]+f[rson][0]+1$,$f[i][0]=max(f[lson][1]+f[rson][0],f[lson][0]+f[rson][1])$

最小是类似的。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
struct Tree_Node {
    int l,r;
    Tree_Node() { this->l=this->r=0; }
}a[500010];
int n=1;
inline void build(int u) {
    char c=getchar();
    int op=c-'0';
    if (op==0) return;
    else if (op==1) { a[u].l=++n; build(a[u].l); }
    else if (op==2) { a[u].l=++n; build(a[u].l); a[u].r=++n; build(a[u].r); }
}
int f[500010][2]; //f[i][0/1]表示以i为根的子树在i为/不为绿色时的最大/最小绿色节点数 
inline void Dfs1(int u) {
    if (!u) return;
    Dfs1(a[u].l); Dfs1(a[u].r);
    f[u][1]=f[a[u].l][0]+f[a[u].r][0]+1;
    f[u][0]=max(f[a[u].l][0]+f[a[u].r][1],f[a[u].l][1]+f[a[u].r][0]);
}
inline void Dfs2(int u) {
    if (!u) return;
    Dfs2(a[u].l); Dfs2(a[u].r);
    f[u][1]=f[a[u].l][0]+f[a[u].r][0]+1;
    f[u][0]=min(f[a[u].l][0]+f[a[u].r][1],f[a[u].l][1]+f[a[u].r][0]);
}
int main() {
    build(1);
    Dfs1(1); printf("%d ",max(f[1][0],f[1][1]));
    memset(f,0,sizeof(0));
    Dfs2(1); printf("%d\n",min(f[1][0],f[1][1]));
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 47 PM

发表评论