题意:给定一个森林。每个节点上安装一个灯可以覆盖与该节点相连的所有边。选择最少的节点数num覆盖所有的边。在num最小的前提下，合理放置num个灯使得被两个灯覆盖的边最多？
思路:F[i][0]代表没放灯，F[i][1]代表放了灯，G[i]类似。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
int f[][],g[][];
int tot,go[],first[],next[];
int n,m;
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int y){
insert(x,y);insert(y,x);
}
void dfs(int x,int fa){
f[x][]=;g[x][]=;
f[x][]=;g[x][]=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
dfs(pur,x);
if (f[pur][]<f[pur][]||(f[pur][]==f[pur][]&&g[pur][]>g[pur][]+)){
f[x][]+=f[pur][];
g[x][]+=g[pur][];
}else{
f[x][]+=f[pur][];
g[x][]+=g[pur][]+;
}
f[x][]+=f[pur][];
g[x][]+=g[pur][];
}
}
int main(){
int T;
scanf("%d",&T);
for (int Tcase=;Tcase<=T;Tcase++){
n=read();m=read();
tot=;
for (int i=;i<=n;i++) first[i]=g[i][]=g[i][]=,f[i][]=f[i][]=-;
for (int i=;i<=m;i++){
int x=read(),y=read();
x++;y++;
add(x,y);
}
int ans1=,ans2=;
for (int i=;i<=n;i++)
if (f[i][]==-&&f[i][]==-){
dfs(i,);
if (f[i][]<f[i][]||(f[i][]==f[i][]&&g[i][]>g[i][])){
ans1+=f[i][];
ans2+=g[i][];
}else{
ans1+=f[i][];
ans2+=g[i][];
}
}
printf("Case %d: %d %d %d\n",Tcase,ans1,ans2,m-ans2);
}
}