题目链接

这个树形dp好妙啊！！！

参考代码

分析

首先通过模拟样例或者手模发现只有两个点的时候才会出现两个好点挨在一起，否则好点之间都是有间隔坏点的
要让权值最小，贪心的想，我们可以把所有坏点的赋值为1；
和树的形状没关系，我们考虑以1为根进行树形dp；

用node dp[u][p]表示：以u为根节点，状态是p时 的子树好节点数cnt和子树权值sum；
（p是1表示u好点，0表示u是坏点，为了方便后面的比较，我们可以重载一下运算符，建议看代码，）

状态转移：
初始化
dp[u][1].cnt = 1;
dp[u][0].sum = 1; //坏点都赋值为1就行
dp[u][1].sum = g[u].size(); //好点的邻点都是坏点，初始值就是坏点的权值和

1. 如果u是好点，则邻点一定是坏点，则转移方程如下

    dp[u][1].cnt += dp[v][0].cnt;
	dp[u][1].sum += dp[v][0].sum;
1
2

2. 如果u是坏点，则邻点可好可坏，选邻点的最优状态来更新u就行（这里就用到了node的比较）

    int p = dp[v][1] > dp[v][0] ? 1 : 0;
	dp[u][0].cnt += dp[v][p].cnt;
	dp[u][0].sum += dp[v][p].sum;
1
2
3

这样树形dp完了，比较一下dp[1][1]，dp[1][0]就知道根节点1取哪种状态最优；
我们根据根节点1的最优状态去重新跑一下，构建一下树就行，具体看代码；

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 998244353;
//const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

struct node
{
	int cnt;	//当前这种状态下好节点的个数
	int sum;	//当前这种状态下的权值
	
	friend bool operator > (node &no1,node &no2)
	{
		if(no1.cnt != no2.cnt) return no1.cnt > no2.cnt;
		return no1.sum < no2.sum;
	}
	
}dp[maxn][2];

vector<int> g[maxn];
int ans[maxn];
int n;

void dfs(int u,int fa)
{
	dp[u][1].cnt = 1;
	dp[u][1].sum = g[u].size();
	dp[u][0].sum = 1;	//坏点都赋值为1就行
	
	for(auto v : g[u])
	{
		if(v == fa) continue;
		dfs(v,u);
		
		dp[u][1].cnt += dp[v][0].cnt;
		dp[u][1].sum += dp[v][0].sum;
		
		//u是坏点的话，v可以是好是坏，选v的最优状态来更新u就行
		int p = dp[v][1] > dp[v][0] ? 1 : 0;
		dp[u][0].cnt += dp[v][p].cnt;
		dp[u][0].sum += dp[v][p].sum;
	}
}

void build(int u,int fa,int p)
{
	ans[u] = p ? g[u].size() : 1;
	for(auto v : g[u])
	{
		if(v == fa) continue;
		
		if(p) build(v,u,0);
		else	//u是坏点的话，v可以是好是坏，选v的最优状态来更新u就行
		{
			int pp = dp[v][1] > dp[v][0] ? 1 : 0;
			build(v,u,pp);
		}
	}
}

void solve()
{
	ire(n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		iire(a,b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	if(n == 2)
	{
		cout<<"2 2\n";
		cout<<"1 1\n";
		return;
	}
	
	//dp出最优结果
	dfs(1,-1);
	
	int p = (dp[1][1] > dp[1][0]) ? 1 : 0;	//最优结果是根节点的哪种状态
	
	//重构一下树
	build(1,-1,p);
    
    cout<<dp[1][p].cnt<<' '<<dp[1][p].sum<<'\n';
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	cout<<'\n';
}

int main()
{
	int T;
//	ire(T);
	T = 1;
	while(T--)
	{
		solve();
	}
	
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157