UVA - 10859 树形dp-与父节点有关&&有两个最优化条件。

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1800
题目大意：


思路：对于两个最优化条件。M* a+b作为指标，很巧妙的思路。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

vector<int> e[1005];
int vis[1005][2], d[1005][2], n, m;

int dp(int i, int j, int f){
    if(vis[i][j]){
        return d[i][j];
    }
    vis[i][j]=1;
    int &ans=d[i][j];

    //i节点放灯
    ans=2000;
    for(int k=0; k<e[i].size(); k++){
        if(e[i][k]!=f){
            ans+=dp(e[i][k], 1, i);
        }
    }

    if(f>=0&&!j){//如果i的父节点不是根并且i的父节点没有放灯
        ans++;   //j-i只有一个灯照亮
    }

    //i节点不放灯
    if(j||f<0){//只有i为根或者i的父节点放灯i才可以不放灯
        int sum=0;
        for(int k=0; k<e[i].size(); k++){
                
            if(e[i][k]!=f){
                sum+=dp(e[i][k], 0, i);
            }
        }
        if(j){//如果i的父亲节点放了灯，那么i-j只被一个灯照亮
            sum++;
        }

        ans=min(sum, ans);
    }

    return ans;

}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){

        memset(e,0 , sizeof(e));
        scanf("%d%d", &n, &m);
        for(int i=1; i<=m; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        memset(vis, 0, sizeof(vis));
        int ans=0;
        for(int i=0; i<n; i++){
            if(!vis[i][0]){//多颗树
                ans+=dp(i, 0, -1);
            }
        }
        printf("%d %d %d\n", ans/2000, m-ans%2000, ans%2000);
    }

    return 0;
}