分析：
改改题面我就能A了 —————yyp
题面说给出一个无向无环图
实际上这就是“森林”啊，ta由多棵树组成
首先，本题的优化目标有两个：
（我们做过这样的题啊）
放置的灯数a尽量少，被两盏灯照亮的边b尽量多，
为了统一起见，我们把第二个条件变成：被一盏灯照亮的边c尽量少
这样有什么用呢
解决双元限制的dp
一般来说，如果有两个变量v1和v2需要优化，
要求首先满足v1最小，在v1相同的情况下v2最小，
这个时候我们一般会把这两个变量合成一个量：
M*v1+v2
（其中M是一个很大的量）
当x=M*v1+v2取最小值的时候
v1=x/M
v2=x%M
M准确的说，是一个比“v2的最大理论值和v2的最小理论值之差”还要大的数
这样，只要两个解得v1不同，则不管v2差多少，都是v1起决定性作用
只有v1相同时，才取决于v2
在本题中，M可以取2000（防止运算时溢出）
每棵树的决策互不影响，所以我们单独处理，最后加和即可
每一个节点只会有两个决策，所以我们设计状态f[i][0/1]
表示i节点的状态是0/1时，i这棵子树的最小x
但是我们发现当前点的状态与父亲的状态有关，没有单独记录当前点的状态
所以新的状态变成了：
f[i][0/1] ：表示父亲结点的状态是0/1，i这棵子树的最小x
每个结点只有两种决策
- 结点i不放灯
只有i是根节点或者i的父亲有灯才有这个选择
此时f[i][1]等于sum{f[k][0]|k取遍i的儿子}
如果i不是根节点，还需要+1，因为i和父亲的连边只被照亮了一次 - 结点i放灯
f[i][j]等于sum{f[k][1]|k取遍i的儿子}+M
(因为多放了一盏灯，所以M的系数v1++)
如果j=0且i不为根，还需要+1，因为i和父亲的这条边只被照亮了一次
Q.
不是说f[i][0/1]只管i这棵子树的信息，为什么还要维护ta和父亲连边的状态呢？
A.
注意这两个+1，都有i不为根的限制
维护和父亲的关系，是方便dp的时候的回溯
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int M=2000;
const int N=1003;
int n,m;
struct node{
int x,y,nxt;
};
node way[N<<1];
int st[N],tot=0,ans;
bool vis[N][N];
int f[N][N];
void add(int u,int w)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}
int dfs(int now,int zt,int fa) //zt fa的状态
{
if (vis[now][zt]) return f[now][zt]; //记忆化
vis[now][zt]=1;
int ans;
ans=M; //放灯总是合法的
for (int i=st[now];i;i=way[i].nxt)
if (way[i].y!=fa)
ans+=dfs(way[i].y,1,now);
if (zt==0&&fa!=-1) ans++;
//当前点的父亲没放灯 而且now不为根
if (zt||fa==-1) //fa放灯了，now就可以不放 或者now是根节点
{
int sum=0;
for (int i=st[now];i;i=way[i].nxt)
if (way[i].y!=fa)
sum+=dfs(way[i].y,0,now);
if (zt&&fa!=-1) sum++; //now不为根
ans=min(ans,sum);
}
f[now][zt]=ans;
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(st,0,sizeof(st));
memset(f,0,sizeof(f));
tot=0; ans=0;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int u,w;
scanf("%d%d",&u,&w);
u++; w++;
add(u,w);
}
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++)
if (!vis[i][0])
ans+=dfs(i,0,-1);
printf("%d %d %d
",ans/M,m-ans%M,ans%M); //灯，照亮两次，照亮一次
}
}