CF1120D Power Tree [树形DP]_「cf1120d」power tree

Power Tree原题 好题

大意

给定一棵树，根是1，每个节点有一个价格，现在你的任务是购买一些节点，使得每个（非根的）叶子节点的数值你可以随意操控（数值不是价格）。对于每个你购买的节点，你可以将这个节点的子树的数值统一变化一个整数$x$。
问：最少要花多少钱可以完成任务；哪些点是某个最优方案可能购买到的。

思考过程

玩一下可以发现一个很简单但是对这题没有用 的性质：每个最优方案的买点数等于叶子节点数。
对于第一问的最小花费显然是可以DP的，DP方程也很简单。
设 $dp[i][0/1]$ 表示控制以$i$ 为根的子树最小花费是多少。其中 0 表示 $i$ 的任何一个祖先都没有购买 ，1表示购买了某一个i的祖先。
0和1的状态非常关键,如果是0，代表所有儿子都要“平起平坐”，自己搞好自己的子树，如果是1，则意味某个祖先可以通过祖先的力量调整整颗子树从而使得某一个儿子不需要自己控制自己，可以通过该祖先的力量和其他兄弟的力量 差 使自己的相对数值变化。(可能没说清楚)
所以写出方程：
$dp[u][0]=min({\sum }_{}dp[son][0],s[u]+dp[son][0]+dp[son][1]+c[u])$
$dp[u][1]=min(s[u]+dp[son][0]+dp[son][1])$
答案是 $dp[1][0]$

对于第二问,哪些点可能被选入最优方案。刚才 DP 是从下往上合并的，而决策是从上至下的，于是从上到下再搜一遍，看看哪些状态可能被选中，这里有可能存在多种状态有着同样的最优花费，都要考虑，细节较多。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,tot=0,first[N],nxt[N<<1],lf[N],d[N],pre[N],vis[N][2],cnt=0,tag[N];
long long c[N],s[N],dp[N][2];
queue <int> q1,q2;
struct Edge
{
	int u,v;
}edge[N<<1];
int Read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return f*x;
}
long long Readl()
{
	long long x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return f*x;
}
void Add(int u,int v)
{
	tot++;
	nxt[tot]=first[u];
	first[u]=tot;
	edge[tot]=(Edge){u,v};
	d[u]++;
	return;
}
void DFS(int u,int fa)
{
	if (lf[u])
	{
		dp[u][0]=c[u];
		dp[u][1]=0;
		return;
	}
	for (int j=first[u];j!=-1;j=nxt[j])
	{
		int v=edge[j].v;
		if (v==fa) continue;
		pre[v]=u;
		DFS(v,u);
		s[u]+=dp[v][0];
	}
	dp[u][0]=s[u];
	for (int j=first[u];j!=-1;j=nxt[j])
	{
		int v=edge[j].v;
		if (v==fa) continue;
		dp[u][1]=min(dp[u][1],s[u]-dp[v][0]+dp[v][1]);
		dp[u][0]=min(dp[u][0],s[u]-dp[v][0]+dp[v][1]+c[u]);
	}
	return;
}
void BFS()
{
	q1.push(1),q2.push(0);
	while (q1.size())
	{
		int tmp1=q1.front(),tmp2=q2.front();
		q1.pop(),q2.pop();
		if (lf[tmp1])
		{
			if (!tmp2) tag[tmp1]=1;
			continue;
		}
		if (dp[tmp1][tmp2]==s[tmp1]&&tmp2==0)
		{
			for (int j=first[tmp1];j!=-1;j=nxt[j])
			{
				int v=edge[j].v;
				if (v==pre[tmp1]) continue;
				if (!vis[v][0]) q1.push(v),q2.push(0),vis[v][0]=1;
			}
		}
		int only=-1;
		for (int j=first[tmp1];j!=-1;j=nxt[j])
		{
			int v=edge[j].v;
			if (v==pre[tmp1]) continue;
			if (tmp2==0)
			{
				if (dp[tmp1][tmp2]==s[tmp1]-dp[v][0]+dp[v][1]+c[tmp1]) 
				{
					if (!vis[v][1]) q1.push(v),q2.push(1),vis[v][1]=1;
					tag[tmp1]=1;
					if (only==1) only=0;
					if (only==-1) only=1;
				}
				if (dp[tmp1][tmp2]!=s[tmp1]-dp[v][0]+dp[v][1]+c[tmp1]) if (!vis[v][0]) q1.push(v),q2.push(0),vis[v][0]=1;
			}
			if (tmp2==1)
			{
				if (dp[tmp1][tmp2]==s[tmp1]-dp[v][0]+dp[v][1]) 
				{
					if (!vis[v][1]) q1.push(v),q2.push(1),vis[v][1]=1;
					if (only==1) only=0;
					if (only==-1) only=1;
				}
				if (dp[tmp1][tmp2]!=s[tmp1]-dp[v][0]+dp[v][1]) if (!vis[v][0]) q1.push(v),q2.push(0),vis[v][0]=1;
			}
		}
		if (only==0)
		{
			for (int j=first[tmp1];j!=-1;j=nxt[j])
			{
				int v=edge[j].v;
				if (v==pre[tmp1]) continue;
				if (!vis[v][0]) q1.push(v),q2.push(0),vis[v][0]=1;
			}
		}
	}
	return;
}
int main()
{
//	freopen("testdata.in","r",stdin);
	memset(first,-1,sizeof(first));
	n=Read();
	for (int i=1;i<=n;i++) c[i]=Readl(),dp[i][1]=dp[i][0]=1e18;
	for (int i=1;i<n;i++) 
	{
		int u,v;
		u=Read(),v=Read();
		Add(u,v),Add(v,u);
	}
	for (int i=2;i<=n;i++) if (d[i]==1) lf[i]=1;
	DFS(1,0);
	BFS();
	for (int i=1;i<=n;i++) if (tag[i]) cnt++;
 	printf("%lld %d\n",dp[1][0],cnt);
 	for (int i=1;i<=n;i++) if (tag[i]) printf("%d ",i);
	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