题目
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1800
题意
n(n < 1000)个节点m条边的无向无环无重边图，最小顶点覆盖的同时要尽量让只有一个端点是点亮的边数最少
思路
如刘书：
1. 无向无环图一定是森林，适用树形DP
2. 因为有两个优化目标，所以将两个目标线性组合，设以i为根的树上的顶点覆盖数为x，单点点亮边数为y，由于y < 1000，所以可以这样组合，令M>1000，优化目标为xM + y，此处M不妨取2e3
3. 通常情况下树形DP只考虑当前节点i的点亮状态和i节点到子节点的关系，但这样就需要在x最小的同时，选取一部分子节点亮让y最小，由于子节点的数量可能较多，点亮的方法也有多种，这使得统计单点点亮边数变成了比较复杂的事情。刘书则记录i节点的父节点的点亮状态，这样，统计单点点亮边数时，统计的是i到父亲这一条是不是单点点亮，而不是i到儿子这若干条是不是，更为方便。
4. 令a[i]为当i的父亲节点点亮时，以i为根的子树满足题意所需的最小综合代价，b为不点亮时代价。那么，明显，令suma为子节点a之和，sumb为子节点b之和
统计a[i]时，由于父亲节点已经点亮，i可以选择点亮或者不点亮。令singleEdgeSupp为父节点点亮而i不点亮的代价，当i为根时singleEdgeSupp=0，否则为1.a[i] = min(mina + M, minb + singleEdgeSupp)，
统计b[i]时，只能点亮i，b[i] = mina + M + 1
假设这颗树真正的根节点为root，那么答案很明显是a[root]，因为可以认为根节点有个虚拟父节点，虚拟父节点是点亮的。
感想
1. 错误地认为边<=1就是叶节点，忽略了根节点只有1个或者没有叶结点的情况。
2. 当只有根节点一个点时，按照Debug上所说的，不需要点灯
代码
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
typedef pair<int, int> MyPair;
int n, m;
const int MAXN = 1e3 + ;
const int M = 2e3;
const int INF = 0x7ffffff;
int edges[MAXN][MAXN];
int edgeCnt[MAXN];
int a[MAXN];//father is lighted up
int b[MAXN];//isn't
bool vis[MAXN]; void dfs(int f, int fa) {
vis[f] = true;
if (edgeCnt[f] <= && fa != -) {
a[f] = ;
b[f] = M + ;
}
else {
int singleEdgeSupp = (fa == - ? : );
int suma = ;//light up itself
int sumb = ;//do not light up
for (int i = ; i < edgeCnt[f]; i++) {
int t = edges[f][i];
if (t == fa)continue;
dfs(t, f);
suma += a[t];
sumb += b[t];
}
a[f] = min(suma + M, sumb + singleEdgeSupp);
b[f] = suma + singleEdgeSupp + M;
}
} int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
int T;
scanf("%d", &T);
for (int ti = ; ti <= T && scanf("%d%d", &n, &m) == ; ti++) {
memset(edgeCnt, , sizeof(edgeCnt));
memset(vis, , sizeof(vis));
for (int i = ; i < m; i++) {
int f, t;
scanf("%d%d", &f, &t);
edges[f][edgeCnt[f]++] = t;
edges[t][edgeCnt[t]++] = f;
}
int ansNode = ;
int ansSingleEdge = ;
for (int i = ; i < n; i++) {
if (!vis[i]) {
dfs(i, -);
int sta = a[i];
/*if (sta == 0) {
sta = M;
}*/
ansNode += sta / M;
ansSingleEdge += sta % M;
}
}
printf("%d %d %d\n", ansNode, m - ansSingleEdge, ansSingleEdge); } return ;
}