FZU 2157 树形DP

最开始一直不理解题是什么意思 ╯▽╰

题意：给出n个点，每个点都有两种花费，一个是0种花费，一个是1种花费，每两个点相连，边也有花费，是随着点所取话费的种类不同，边的花费也不同，边有四种花费，00，01，10，11    问建成整颗树所需要的最少花费。

思路：dp[i][0]代表当前结点取0种花费时建好以i结点为根节点的最少花费，dp[i][1]代表当前结点取1种花费时建好以i结点为根节点的最少花费，那么有动态转移方程就出来了.......

 Sample Input

1

4

3 1 1 3

4 0 0 4

1 2 0 1 1 0

2 3 0 1 1 0

2 4 0 1 1 0

 Sample Output

8

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
struct node
{
    int y;
    int a,b,c,d;
};

vector<node>q[200005];
int dp[200005][2];
int num1[200005];
int num2[200005];

void dfs(int u)
{
    if(q[u].empty())
    {
        dp[u][0] = num1[u];
        dp[u][1] = num2[u];
        return;
    }
    dp[u][0] = num1[u];
    dp[u][1] = num2[u];
    int len = q[u].size();
    for(int i = 0; i < len; i++)
    {
        node tmp = q[u][i];
        dfs(tmp.y);
        dp[u][0] += min(dp[tmp.y][0]+tmp.a,dp[tmp.y][1]+tmp.b);
        dp[u][1] += min(dp[tmp.y][0]+tmp.c,dp[tmp.y][1]+tmp.d);
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i =1; i <= n; i++)
            scanf("%d",&num1[i]);
        for(int i = 1; i <= n; i++)
            scanf("%d",&num2[i]);
        memset(dp,0,sizeof(dp));


        for(int i = 0;i <= n;i++)
            q[i].clear();

        int x,y,a,b,c,d;
        for(int i = 1; i < n; i++)
        {
            scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
            node temp;
            temp.y = y;
            temp.a = a;
            temp.b = b;
            temp.c = c;
            temp.d = d;
            q[x].push_back(temp);
        }

        dfs(1);
        printf("%d
",min(dp[1][0],dp[1][1]));
    }


    return 0;
}