[UVA10859 放置街灯 Placing Lampposts]

一.前言

啊啊啊啊啊啊我竟然会做树形DP！！！！！（好吧不会其实

有一说一UVA是真的慢奥，放个题目链接

二.思路

首先，什么是无向无环图呢？我个人倾向认为是“森林”。很显然的，一棵树上将任意两个点额外加一条边连起来就会有一个环出现，而一个图的生成树（包含原图所有点）就是这个图中的最大无向无环图（毕竟再加边就有环了），但是这道题不是最大，相当于是从树上取几条边删掉，就形成了森林。

明确了是森林之后，需要将整个森林分为几颗树来解决。对于一个点及他的子树，我们设 (f[x][0],g[x][0]) 分别为 x点无灯时的它的子树（包含它）中最小灯数以及被两个灯所覆盖的道路数。（有灯二维为1）

之所以只记录被两个灯所覆盖的，而不是记录三个值，是因为后两个的和为边的总数。

由于每一条边都要有灯，显然的，(f[x][0]) 只能由 (f[children[x]][1]) 转移过来。而 (f[x][1]) 则有可能由 (f[children[x]][1/0])转移过来，这个转移涉及到被两个灯照耀的边数+1，而这个又是第二关键字。种种因素结合起来，得出一段转移代码。

for(int i=head[x];i!=-1;i=ne[i]){
		int v=to[i];
		if(v==fa)continue;
		dfs(v,x);
		f[x][0]+=f[v][1];g[x][0]+=g[v][1];
		if(f[v][1]>f[v][0])f[x][1]+=f[v][0],g[x][1]+=g[v][0];
		else if(f[v][1]==f[v][0]&&g[v][0]>g[v][1]+1)
			f[x][1]+=f[v][0],g[x][1]+=g[v][0];
		else f[x][1]+=f[v][1],g[x][1]+=g[v][1]+1;
	}

（应该还算简明易懂）

然后设置边界条件为 (f[x][1]=1) 这是初始值，很显然。

最后整体采用自叶到根的转移，（DFS），因为从儿子转移过来，并且儿子的决策对父亲没有影响。因为森林，要对每一个树分别dfs。

三.CODE

const int MAXN=1005;
int t,n,m,ans1,ans2;
int head[MAXN],to[2*MAXN],ne[2*MAXN],tot;
int f[MAXN][2],g[MAXN][2];
bool vis[MAXN];
void add(int x,int y){
	to[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
}
void dfs(int x,int fa){
	vis[x]=1;
	f[x][1]=1;
	for(int i=head[x];i!=-1;i=ne[i]){
		int v=to[i];
		if(v==fa)continue;
		dfs(v,x);
		f[x][0]+=f[v][1];g[x][0]+=g[v][1];
		if(f[v][1]>f[v][0])f[x][1]+=f[v][0],g[x][1]+=g[v][0];
		else if(f[v][1]==f[v][0]&&g[v][0]>g[v][1]+1)
			f[x][1]+=f[v][0],g[x][1]+=g[v][0];
		else f[x][1]+=f[v][1],g[x][1]+=g[v][1]+1;
	}
}
int main(){
	t=read();
	while(t--){
		n=read();m=read();
		ans1=ans2=tot=0;
		memset(head,-1,sizeof(head));
		memset(vis,0,sizeof(vis));
		memset(g,0,sizeof(g));
		memset(f,0,sizeof(f));
		for(int i=1,u,v;i<=m;++i){
			u=read();v=read();
			add(u,v);add(v,u);
		}
		for(int i=0;i<n;++i){
			if(!vis[i]){
				vis[i]=1;
				dfs(i,-1);
				if(f[i][0]<f[i][1])ans1+=f[i][0],ans2+=g[i][0];
				else if(f[i][0]==f[i][1]&&g[i][0]>g[i][1])
					ans1+=f[i][0],ans2+=g[i][0];
				else ans1+=f[i][1],ans2+=g[i][1];
			}
		}
		cout<<ans1<<" "<<ans2<<" "<<m-ans2<<endl;
	}
	return 0;
}