#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

struct node

{

    int x,y,next;

};

node a[];

int len,last[];

void add(int x,int y)

{

    a[++len].x = x;

    a[len].y = y;

    a[len].next = last[x];

    last[x] = len;

}

int fa[],son[];

int f[][];

int v[];

/*

f[i][1]代表请i的最大值

f[i][0]代表不请i的最大值

*/

template <class T>

void read(T &x)

{

    char c;

    int op = ;

    while(c = getchar(),c > '' || c < '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(),c >= '' && c <= '')

        x = x *  + c - '';

    if(op == )

        x = -x;

}

void treedp(int x)

{

    f[x][] = v[x];

    for(int k = last[x];k;k = a[k].next) //相当于dfs

        treedp(a[k].y);

    for(int k = last[x];k;k = a[k].next)

    {

        int y = a[k].y;

        f[x][] += f[y][]; //dp转移式①

    }

    f[x][] = ;

    for(int k = last[x];k;k = a[k].next)

    {

        int y = a[k].y;

        f[x][] += max(f[y][],f[y][]);//dp转移式②

    }

}

int main()

{

    int n;

    read(n);

    memset(f,-,sizeof(f));

    memset(fa,,sizeof(fa));

    for(int i = ;i <= n;i++)

        read(v[i]);

    int xx,yy;len = ;

    memset(last,,sizeof(last));

    while(scanf("%d%d",&xx,&yy) != EOF)

    {

        if(xx ==  && yy == )

        {

            break;

        }

        add(yy,xx);

        fa[xx] = yy; //找根节点

    }

    int root = ;

    for(int i = ;i <= n;i++)

        if(fa[i] == )

        {

            root = i;

            break;

        }

    treedp(root);

    printf("%d\n",max(f[root][],f[root][]));

    return ;

}

【问题描述】

设一个有n个节点的二叉树的中序遍历为（l,,,…,n），其中数字1,,,…,n为节点编号。

每个节点都有一个分数（均为正整数），记第i个节点的分数为di， 每棵子树都有一个加分，任一棵子树subtree的加分计算方法如下：

    subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数

    若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

    试求一棵符合中序遍历为（,,,…,n）且加分最高的二叉树tree。要求输出；

    （）tree的最高加分

    （）tree的前序遍历

【输入格式】

    第1行：一个整数n（n＜），为节点个数。

    第2行：n个用空格隔开的整数，为每个节点的分数（分数＜）。

【输出格式】

    第1行：一个整数，为最高加分（结果不会超过2,  ）。

    第2行：n个用空格隔开的整数，为该树的前序遍历。

【样例输入】

【样例输出】

#include<cstdio>

#include<iostream>

using namespace std;

int root[][],d[],f[][];

void pre_visit(int l,int r)

{

    if(l <= r)

    {

        cout<<root[l][r]<<" ";

        pre_visit(l,root[l][r] - );

        pre_visit(root[l][r] + , r);

    }

}

int main()

{

    int m;

    cin>>m;

    for(int i = ;i <= m;i++)

    {

        for(int j = ;j <= m;j++)

        {

            f[i][j] = ;

        }

    }

    for(int i = ;i <= m;i++)

    {

        cin>>d[i];

        root[i][i] = i;

        f[i][i] = d[i];

    }

    for(int k = ;k <= m;k++)

    {

        for(int l = ;l <= m - k + ;l++)

        {

            int r = l + k - ;

            for(int i = l;i <= r;i++)

            {

                if(f[l][r] < f[l][i - ] * f[i + ][r] + d[i])

                {

                    root[l][r] = i;

                    f[l][r] = f[l][i - ] * f[i + ][r] + d[i];

                }

            }

        }

    }

    cout<<f[][m]<<endl;

    cout<<root[][m]<<" ";

    pre_visit(,root[][m] - );

    pre_visit(root[][m] + ,m);

}

【问题描述】

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。 皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；有边直接相连的宫殿可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。 可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

【输入格式】

输入文件中数据表示一棵树，描述如下：

第1行 n，表示树中结点的数目。

第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（<I<=N），在该宫殿安置侍卫所需的经费K，该点的儿子数M，接下来M个数，分别是这个节点的M个儿子的标号R1，R2，...，RM。对于一个n（ < n<=）个结点的树，结点标号在1到n之间，且标号不重复。

【输出格式】

输出文件仅包含一个数，为所求的最少的经费。

输入样例：

输出样例：

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

struct node

{

    ll x,y,next;

};

node a[];

ll v[],f[][];

ll last[],len = ;

bool bk[];

/*

i节点安全代表i节点和子树安全

不安全代表i节点不安全，但是子树安全

f[i][0]表示x点不放人，但是安全

f[i][1]表示x点不放人，不安全

f[i][2]表示x点放人，所以安全

f[i][3]表示x点放人，但是不安全，显然不成立

*/

void treedp(int x)

{

    f[x][] = v[x];

    f[x][] = ;f[x][] = ;

    ll minn = ;

    bool bkk = false;

    for(int k = last[x];k;k = a[k].next)

    {

        ll y = a[k].y;

        if(bk[y] == false)

        {

            bk[y] = true;

            treedp(y);

            minn = min(f[y][] - f[y][],minn);

            f[x][] += min(f[y][],f[y][]);

            if(f[y][] <= f[y][])

            {

                bkk = true;

            }//一定选f[i][2]

            f[x][] += f[y][];

            f[x][] += min(f[y][],min(f[y][],f[y][]));

        }

    }

    if(bkk == false)

    {

        f[x][] += minn;

    }

}

void add(int x,int y)

{

    a[++len].x = x;

    a[len].y = y;

    a[len].next = last[x];

    last[x] = len;

}

int main()

{

    ll n;

    cin>>n;

    memset(f,,sizeof(f));

    for(int i = ;i <= n;i++)

    {

        ll x,m,k;

        cin>>x>>k>>m;

        v[x] = k;

        for(int j = ;j <= m;j++)

        {

            ll y;

            cin>>y;

            add(x,y);

            add(y,x);

        }

    }

    ll root = ;

    memset(bk,false,sizeof(bk));

    bk[root] = true;

    treedp(root);

    cout<<min(f[root][],f[root][]);

    return ;

}