codeforces 1120D Power Tree 题解

题目传送门

题目大意： 给出一棵树，根是 $1$，如果你控制一个点，那么你可以给他的子树加一个随意的权值，且控制这个点有一个代价 $w_i$。问你需要花费最少多少代价，使得无论每个叶子结点的初始点权是多少，你都可以通过操作使它们权值清 $0$。

题解

做法十分巧妙。

先求一遍 $dfs$ 序，把叶子节点按照 $dfs$ 序拎出来造一个序列，那么就转化成了一个区间问题，再差分一下，假如控制了一个节点，他管理的区间为 $[l,r]$，则给 $[l,r]$ 加一个权值 $x$ 相当于在差分数组上给 $b_l+=x,b_{r+1}-=x$。

假如给所有 $l,r+1$ 之间连边，权值为控制该节点的代价，求一遍最小生成树就能得到答案。

证明很简单，假如差分数组上任意两点都连通，那么就可以修改原数组中任意一位的数值。

单独考虑原数组中一个位置 $x$，假如让他加上 $c$，那么差分数组上会有两点发生改变，一个点 $+c$，一个点 $-c$。由于差分数组上任意两点连通，你可以通过操作将差分数组上的权值沿着边进行移动，那么将 $+c$ 移动到 $-c$ 位置，他们就抵消了，这样就让 $x$ 位置重新变成了 $0$。

代码如下：

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define maxn 200010 #define pb push_back int n,w[maxn]; struct edge{int y,next;}e[maxn<<1]; int first[maxn],len=0; void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;} int id[maxn],idtot=0,con[maxn]; vector<int> c,ans; void dfs(int x,int fa){ id[x]=++idtot; for(int i=first[x];i;i=e[i].next)if(e[i].y!=fa)dfs(e[i].y,x); con[x]=idtot; if(id[x]==con[x])c.pb(id[x]); } int b[maxn],fa[maxn]; int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);} bool cmp(int x,int y){return w[x]<w[y];} long long tot=0; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&w[i]),b[i]=i; for(int i=1,x,y;i<n;i++){ scanf("%d %d",&x,&y); buildroad(x,y);buildroad(y,x); } dfs(1,0);sort(b+1,b+n+1,cmp);sort(c.begin(),c.end()); for(int i=1;i<=n+1;i++)fa[i]=i; #define findc(x) (lower_bound(c.begin(),c.end(),x)-c.begin()+1) for(int i=1;i<=n;i++){ int j=i;while(j<n&&w[b[j+1]]==w[b[i]])j++; for(int k=i;k<=j;k++){ int x=findc(id[b[k]]),y=findc(con[b[k]]+1); x=findfa(x);y=findfa(y); if(x!=y)ans.pb(b[k]); } for(int k=i;k<=j;k++){ int x=findc(id[b[k]]),y=findc(con[b[k]]+1); x=findfa(x);y=findfa(y); if(x!=y)fa[y]=x,tot+=w[b[k]]; } i=j; } printf("%lld %d\n",tot,ans.size()); sort(ans.begin(),ans.end()); for(int i:ans)printf("%d ",i); }