题目地址：http://vjudge.net/problem/UVA-10859
很明显是DP；但关键是怎么DP
题目优化的方向是a放置的灯数尽量少，被两盏灯照亮的边数b尽可能大，也就是c被一盏灯照亮的路尽可能小，a-b=c，所以c越小，b越大
综上就是，x=a+c越小越好
而且题目要求a为首要条件，b为次要条件，于是增加a的比重 x=M*a+c，便成为x=M*a+c越小越好，注意M不是越大越好，防止算数超出
既然书树形，一般都要无根树转有根树，求出fa数组保存父节点，于是状态定义为d[i] 为i为根最小的x值(包括i到其父节点的这条边)
对于一个点放不放灯，需要看上一个节点也就是父节点，所以状态定义为d[i][j]，j=1表示i父节点节点放灯，0表示无
注意不能用j代表i节点是否放灯，这样就会有后效性，将放不放灯的决策留到下一个状态，这样不好判断，比如i没放灯，那么i的子结点k至少其中一个要放灯，无法确定是哪个k放灯，只会让状态转移十分混乱，所以不如定义j为i父节点是否放灯了，这样i的子结点k的状态十分明了，只需要看i放灯没
状态转移：d[i][j]=∑{d[k,j']} k为i的子结点 具体看代码
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=1000+5,M=2000;
std::vector<vector<int> > Adj(maxn);
int d[maxn][2]; //x=M*a+c
bool vis[maxn][2];
int DP(int i,int j,int fa){int& ans=d[i][j];if(vis[i][j]) return ans;vis[i][j]=true;ans=j==1?M:(M+(fa!=-1?1:0));REP(k,0,Adj[i].size()-1) { //放灯，放灯是一定可行的 int v=Adj[i][k];if(v!=fa) ans+=DP(v,1,i);}if(fa==-1||j==1) { //不放灯int notPut=fa!=-1?1:0; //+c;REP(k,0,Adj[i].size()-1){ int v=Adj[i][k];if(v!=fa) notPut+=DP(v,0,i); }ans=min(ans,notPut);}return ans; //放和不放取x最小
}
int main(int argc, char const *argv[])
{int T; scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);REP(i,0,n) Adj[i].clear();REP(i,1,m){int u,v; scanf("%d%d",&u,&v);Adj[u].push_back(v);Adj[v].push_back(u);}memset(vis,false,sizeof(vis));int ans=0;REP(i,0,n-1) if(!vis[i][0]) ans+=DP(i,0,-1);printf("%d %d %d\n", ans/M,m-ans%M,ans%M);}return 0;
}