[数据结构与算法]CF 1646D Weight the Tree 树形dp

题目链接

这道题拖了很长时间才去补，今天想起来做这道题

这道题的题意是可以组成合法的点互不相邻，我的思路没有错误，但是赛时没有写出代码，现在想想也觉得可惜，我要是多想到一个度的条件，赛时可能就会过了orz 。

首先前置芝士
没有上司的舞会
这道题和那个题几乎一模一样的代码，一样的推导过程，不过增加了限制，我赛时也是想出了雏形但是没有做出来。

然后分析推导过程

$f(u,0)$ 表示当前点不选的子树（包含自己） ， 可以选择的最多的点。
$f(u,1)$ 表示当前点选的子树（包含自己） ， 可以选择的最多的点。

关系式子

$f(u,1)$ = 求和 $f(j,0)$
$f(u,0)$ = 求和 $max(f(j,0),f(j,1))$

然后求和就是找度数之和最小的点，首先我们可以贪心不能组成的点为1，这样就可以贪心的让组成的点为它的度数啦 ， 然后我们就可以开始愉快的敲代码 ac 了

代码如下

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std ;

const int N = 2e5 + 10 ;
const int M = 2 * N ;

int f[N][2] ;
int g[N][2] ;
int h[N] , e[M] , ne[M] , idx , d[N] ;
int ans[N] ;

void add(int a , int b)
{
	e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
	d[a] ++ ; 
}

void dfs(int u , int fa)
{
	f[u][1] = 1 ;
	g[u][1] = d[u] ;
	g[u][0] = 1 ;
	for(int i = h[u] ; ~i ; i = ne[i])
	{
		int j = e[i] ;
		if(j == fa) continue ;
		dfs(j , u) ;
		f[u][1] += f[j][0] ;
		g[u][1] += g[j][0] ;
		f[u][0] += max(f[j][0] , f[j][1]) ;
		if(f[j][0] > f[j][1])
			g[u][0] += g[j][0] ;
		else if(f[j][0] < f[j][1])
			g[u][0] += g[j][1] ;
		else 
			g[u][0] += min(g[j][0] , g[j][1]) ;
	}
}

void dfs(int u , int fa , int ty)
{
	if(!ty) ans[u] = 1 ;
	else ans[u] = d[u] ;
	for(int i = h[u] ; ~i ; i = ne[i])
	{
		int j = e[i] ;
		if(j == fa) continue ;
		if(ty)
			dfs(j , u , 0) ;
		else 
		{
			if(f[j][0] > f[j][1])
				dfs(j , u , 0) ;
			else if(f[j][0] < f[j][1])
				dfs(j , u , 1) ;
			else if(g[j][0] < g[j][1])
				dfs(j , u , 0) ;
			else 
				dfs(j , u , 1) ;
		}
	}
}
int main(void)
{
	memset(h , -1 , sizeof h) ;
	int n ;
	scanf("%d" , &n) ;
	for(int i = 1 ; i < n ; i ++)
	{
		int a , b ;
		scanf("%d%d" , &a , &b) ;
		add(a , b) , add(b , a) ;
	}
	if(n == 2)
	{
		puts("2 2") ;
		puts("1 1") ;
		return 0 ;
	}
	dfs(1 , 1) ;
	if(f[1][0] > f[1][1])
		dfs(1 , 1 , 0) , printf("%d %d\n" , f[1][0] , g[1][0]);
	else if(f[1][0] < f[1][1])
		dfs(1 , 1 , 1) , printf("%d %d\n" , f[1][1] , g[1][1]);
	else if(g[1][0] < g[1][1])
		dfs(1 , 1 , 0) , printf("%d %d\n" , f[1][0] , g[1][0]);
	else 
		dfs(1 , 1 , 1) , printf("%d %d\n" , f[1][1] , g[1][1]);
	for(int i = 1 ; i <= n ; i ++)
		printf("%d " , ans[i]) ;
}