题解 CF1120D 【Power Tree】
ez_lcw
2021-01-23 17:25:22
很巧妙的一种方法。
首先我们可以把叶子节点按 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 的过程中判断一下就好了。~~(我差点写了最小生成树的树剖)~~
代码如下:
```cpp
#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;
}
```