【CF1120D】Power Tree（建图，差分，最小生成树）_power tree讲解

题面

题意有点难懂。

主要是洛谷给的翻译太zz了。

大概的意思是：

给定一棵 $n$ 个点的有根树，$1$ 为根，每一个点有一个代价 $c_i$。

然后有两个人 Alice 和 Bob 在玩游戏。

在第一阶段，Alice 会购买树上的一些点，购买一个点的代价是 $c_i$。

在第二阶段，Bob 将给树的所有叶子节点设置一个点权。

在第三阶段，Alice 可以选择他在第一阶段购买的一些点。对于他选择的每一个点 $u$，他可以让 $u$ 子树内的所有叶子节点的点权加上他任意指定的一个整数 $x$。

你需要帮 Alice 选择购买一些点，使得不管在第二阶段 Bob 怎样设置叶子节点的点权，总有一种方法使得 Alice 在第三阶段把所有叶子节点的点权归零，而且购买花费的代价尽量小。

题解

很巧妙的一种方法。

首先我们可以把叶子节点按 dfs 序抽象成一个序列，不妨设这个序列长 $k$。

那么控制一棵子树内的叶子节点的点权等同于控制序列一段区间的点权。

全体置零的要求和区间加的操作容易联想到差分数组，不妨设差分数组 $b_i=a_i-a_{i-1}$，$a_0=0$。

对于操作区间 $[l,r]$ 加 $x$，就可以看作是 $b_l$ 加 $x$，$b_{r+1}$ 减 $x$，那么我们就得新建出一个虚点 $k+1$。

对于要求全体置零，就可以看做是要求 $\forall i\in [1,k],b_i=0$。

发现每次操作后差分数组的总和不会变，所以为了达到要求，必须把所有的值转移到 $b_{k+1}$ 上去。

对于操作区间 $[l,r]$ 加 $x$，我们可以连边 $(l,r+1)$，边权为 $x$。

不难发现当且仅当两个点联通时，才能把一个点的 $b$ 值转移到另一个点上去，且代价为边权和（注意代价与 $b$ 值大小无关，所以这道题不是用网络流）。

所以题目的要求就是所有的点都要和 $k+1$ 联通，然后问最小代价。

那么这就是一个最小生成树能解决的事情了。

至于输出所有可能在最优方案中的点，也就是输出所有可能出现在最小生成树中的边，可以直接在 kruskal 的过程中判断一下就好了。（我差点写了最小生成树的树剖）

代码如下：

#include<bits/stdc++.h>

#define N 200010
#define ll long long

using namespace std;

struct Edge
{
	int u,v,w,id;
	Edge(){};
	Edge(int a,int b,int c,int d){u=a,v=b,w=c,id=d;}
}e[N];

int n,m,c[N],fa[N];
int cnt,head[N],nxt[N<<1],to[N<<1];
int idx,lp[N],rp[N],size[N];
bool vis[N];
int num;
ll ans;

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void dfs(int u,int fa)
{
	bool leaf=true;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		leaf=0;
		dfs(v,u);
		if(!lp[u]) lp[u]=lp[v];
		rp[u]=rp[v];
	}
	if(leaf) lp[u]=rp[u]=++idx;
	e[++m]=Edge(lp[u],rp[u]+1,c[u],u);
}

bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	return x==fa[x]?x:(fa[x]=find(fa[x]));
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		adde(u,v),adde(v,u);
	}
	dfs(1,0);
	sort(e+1,e+m+1,cmp);
	idx++;
	for(int i=1;i<=idx;i++) fa[i]=i;
	for(int l=1,r;l<=m;l=r+1)
	{
		r=l;
		while(r+1<=m&&e[r].w==e[r+1].w) r++;
		for(int i=l;i<=r;i++)
		{
			int a=find(e[i].u),b=find(e[i].v);
			if(a!=b)
			{
				num++;
				vis[e[i].id]=1;
			}
		}
		for(int i=l;i<=r;i++)
		{
			int a=find(e[i].u),b=find(e[i].v);
			if(a!=b)
			{
				fa[a]=b;
				ans+=e[i].w;
			}
		}
	}
	printf("%lld %d\n",ans,num);
	for(int i=1;i<=n;i++)
		if(vis[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