[CF1120D]Power Tree_「cf1120d」power tree

题目

传送门 to luogu

思路壹

树形 $\mathtt{d}\mathtt{p}$ 的想法是很明显的，也不需要证明什么性质。可以感性理解。

用 $f(x,0)$ 表示，将 $x$ 子树内的所有叶子搞成同样的权值。为啥要这么想？因为控制 $x$ 的祖先的话，$x$ 子树内的叶子节点都是同加同减的。最终要变成全 $0$ ，所以目前必须变得相同。

感性理解不难发现，$f(x,0)$ 肯定是子树内的某一个点没有被修改，其他点都改成了这个点。当然你也可以不用知道这一条。

$f(x,1)$ 表示，将 $x$ 子树内的所有叶子全部搞成 $0$ （或者其他任意一个指定值）。那么转移方程式可以写出

$$f(x,0)=\underset{y\in son}{\min }[f(y,0)+\sum _{t\ne y}f(t,1)]$$

无非就是一个子树直接操作成相同的，其他人操作成这个值。另一个方程式为

$$f(x,1)=\min [c_x+f(x,0),\sum _{t\in son}f(t,1)]$$

无非就是每个子树都操作成 $0$ ，或者只单纯地搞成相同，然后用根解决问题。

输出方案？用类似 $\mathtt{b}\mathtt{f}\mathtt{s}$ 的方式，将“最优方案的一种含有之”的状态放进队列。分类讨论比较麻烦，不过也是可以做的。

代码壹

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MaxN = 200005;
const int_ infty = (1ll<<60)-1;
vector< int > g[MaxN];
int c[MaxN];

int_ dp[MaxN][2]; int fa[MaxN];
vector< int > pre[MaxN][2];
void dfs(int x){
	int_ t = infty;
	for(auto y : g[x]){
		if(y == fa[x]) continue;
		fa[y] = x; dfs(y);
		dp[x][1] += dp[y][1];
		if(t > dp[y][0]-dp[y][1]){
			t = dp[y][0]-dp[y][1];
			pre[x][0].clear();
		}
		if(t == dp[y][0]-dp[y][1])
			pre[x][0].push_back(y);
	}
	if(t == infty) // 是个叶子
		return void(dp[x][1] = c[x]);
	dp[x][0] = dp[x][1]+t;
	if(dp[x][1] <= dp[x][0]+c[x])
		pre[x][1].push_back(-1);
	if(dp[x][1] >= dp[x][0]+c[x]){
		dp[x][1] = dp[x][0]+c[x];
		pre[x][1].push_back(x);
	}
}

bool vis[MaxN][2], ans[MaxN];
queue< int > q;
void expandTo(int x,int y){
	if(!vis[x][y]){
		vis[x][y] = true;
		q.push(y*MaxN+x);
	}
}
void bfs(){
	q.push(MaxN+1), vis[1][1] = 1;
	while(!q.empty()){
		int x = q.front(); q.pop();
		int y = x/MaxN; x -= y*MaxN;
		if(g[x].size() == 1u && x != 1){
			if(y == 1) ans[x] = 1;
			continue; // 叶子，不必扩展
		}
		/* dp[x][1] 的同层转移 */ ;
		if(y == 1 && pre[x][y].back() == x)
			expandTo(x,0), ans[x] = 1;
		/* dp[x][1] 的非同层转移 */ ;
		if(y == 1 && pre[x][y][0] == -1)
			for(auto p : g[x]) if(p != fa[x])
				expandTo(p,1);
		/* dp[x][0] 可多处选0，则均可为1 */
		if(y == 0 && pre[x][y].size() != 1u)
			for(auto p : g[x]) if(p != fa[x])
				expandTo(p,1);
		/* dp[x][0] 仅可一处为0，其余为1 */
		if(y == 0 && pre[x][y].size() == 1u)
			for(auto p : g[x]) if(p != fa[x])
				if(p != pre[x][y][0])
					expandTo(p,1);
		/* 处理所有可以选0的位置 */
		if(y == 0)
			for(auto p : pre[x][y])
				expandTo(p,0);
	}
}

int main(){
	int n = readint();
	for(int i=1; i<=n; ++i)
		c[i] = readint();
	for(int i=1,a,b; i<n; ++i){
		a = readint(), b = readint();
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1), printf("%lld ",dp[1][1]);
	bfs(); int calc = 0;
	for(int i=1; i<=n; ++i)
		if(ans[i]) ++ calc;
	printf("%d\n",calc);
	for(int i=1; i<=n; ++i)
		if(ans[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

思路贰

记得对子树操作的题有一个技巧，将其转化为一段连续的 $\mathtt{d}\mathtt{f}\mathtt{s}$ 序。这道题也可以借鉴这个思想。

控制一个点，认为可以对叶子序列上的一个区间进行操作。转化成差分，相当于可以让一个差分值增加、一个减少。也就是在用边来传递权值。由于差分数组的总和是 $0$ ，所以只要连接成一个连通块就一定能完成任务。另一方面，由于权值可以任取，如果不成为连通块，则可以使得一个连通块的权值和不为 $0$ ，一定死翘翘。

于是就变成了最小生成树的题了。输出方案，就是判断是否存在包含此边的最小生成树。也怪难写的。

代码贰

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int_;
inline int_ readint(){
	int_ a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MaxN = 200010;

namespace UFS{
	int fa[MaxN];
	void init(int n){
		for(int i=1; i<=n; ++i)
			fa[i] = i;
	}
	int find(int a){
		if(a == fa[a]) return a;
		return fa[a] = find(fa[a]);
	}
	/** @return Whether they're disconnected*/
	bool combine(int a,int b){
		if(find(a) != find(b))
			fa[fa[a]] = fa[b];
		else return false;
		return true;
	}
}

struct Edge{
	int to, nxt, val, from;
	Edge(int T=0,int N=0,int V=0){
		to = T, nxt = N, val = V;
	}
	operator int(){ return val; }
} edge[MaxN<<1|1];
int head[MaxN], cntEdge;
/** @brief add an undirected edge with value @n c */
void addEdge(int a,int b,int c=0){
	edge[cntEdge] = Edge(b,head[a],c);
	head[a] = cntEdge ++;
	edge[cntEdge] = Edge(a,head[b],c);
	head[b] = cntEdge ++;
}

int c[MaxN], tot;
Edge e[MaxN]; // 转化为最小生成树的边
int st[MaxN], ed[MaxN]; // 能控制的叶子区间
void dfs(int x,int pre){
	st[x] = MaxN, ed[x] = -1;
	for(int i=head[x]; ~i; i=edge[i].nxt){
		if(edge[i].to == pre) continue;
		dfs(edge[i].to,x);
		if(st[edge[i].to] < st[x])
			st[x] = st[edge[i].to];
		if(ed[x] < ed[edge[i].to])
			ed[x] = ed[edge[i].to];
	}
	if(ed[x] == -1) // 自己是叶子
		st[x] = ed[x] = ++ tot;
	e[x] = Edge(ed[x]+1,x,c[x]);
	e[x].from = st[x]; // 特殊用处
}

int fa[20][MaxN], val[20][MaxN], dep[MaxN];
void build(int x,int pre){
	for(int j=0; j+1<20; ++j){
		if(fa[j][x] == 0) break;
		fa[j+1][x] = fa[j][fa[j][x]];
		val[j+1][x] = val[j][fa[j][x]];
		if(val[j+1][x] < val[j][x])
			val[j+1][x] = val[j][x];
	}
	for(int i=head[x]; ~i; i=edge[i].nxt){
		if(edge[i].to == pre) continue;
		fa[0][edge[i].to] = x;
		val[0][edge[i].to] = edge[i].val;
		dep[edge[i].to] = dep[x]+1;
		build(edge[i].to,x);
	}
}

int query(int a,int b){
	if(dep[a] < dep[b]) swap(a,b);
	int res = 0;
	for(int j=19; ~j; --j)
		if((dep[a]-dep[b])>>j&1){
			res = max(res,val[j][a]);
			a = fa[j][a];
		}
	if(a == b) return res;
	for(int j=19; ~j; --j)
		if(fa[j][a] != fa[j][b]){
			res = max(res,val[j][a]);
			a = fa[j][a];
			res = max(res,val[j][b]);
			b = fa[j][b];
		}
	return max(res,max(val[0][a],val[0][b]));
}

bool inSet[MaxN];
int main(){
	int n = readint();
	for(int i=1; i<=n; ++i){
		c[i] = readint();
		head[i] = -1;
	}
	for(int i=1; i<n; ++i)
		addEdge(readint(),readint());
	dfs(1,-1); // 进行等价转换
	for(int i=1; i<=n; ++i)
		head[i] = -1; // 清空图
	cntEdge = 0; // 建立新图
	UFS::init(tot+1); sort(e+1,e+n+1);
	int xez = 0; int_ ans = 0;
	for(int i=1; i<=n; ++i)
		if(UFS::combine(e[i].from,e[i].to)){
			ans += e[i].val, ++ xez;
			addEdge(e[i].from,e[i].to,e[i].val);
			if(xez == tot) break;
		}
	printf("%lld ",ans);
	build(1,-1); int calc = 0;
	for(int i=1; i<=n; ++i)
		if(query(e[i].from,e[i].to) == e[i].val)
			inSet[e[i].nxt] = true, ++ calc;
	printf("%d\n",calc);
	for(int i=1; i<=n; ++i)
		if(inSet[i]) printf("%d ",i);
	putchar('\n');
	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