【Codeforces 1120D】Power Tree | Mrsrz's blog

差分，最小生成树。

题目大意：

给定一棵树，每个叶子结点有一个正的权值。

现在可以选择若干个结点，然后对每个结点，选择一个值 $v$，则这个结点所在子树中所有结点的权值都加上 $v$。

选择每个结点，都有一个代价 $c_i$。要求选择的结点的代价之和最小，使得不管叶子结点的权值怎么样，都存在一种方法操作你选择的结点，使得所有叶子结点的权值变为 $0$。

输出最小的代价，并输出所有可能在最优方案中的点。

题解：

我们对叶子结点按访问的顺序编号，然后对于每个结点，它影响到的所有叶子结点的编号一定是一个连续的区间。

然后不管叶子的权值如何，我们可以对其进行差分，则一个影响 $[l,r]$ 的点，实际上是给 $l$ 的权值加 $v$，给 $r+1$ 的权值减 $v$。

那么要使权值任意情况都可以控制，我们需要令每个点都对应一个区间的左端点。

这些区间有一些特点，任意两个区间要么无交，要么存在包含关系。

不难发现如果我们对所有区间，连边 $l$ 和 $r+1$，那么最后选的边必须形成一个连通图。

所以求最小生成树即可。

至于输出方案，就是求所有可能在 MST 上的边。我们对边权相同的边同时考虑即可。

时间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N=2e5+5;
struct edge{
    int to,nxt;
}e[N<<1];
int n,head[N],cnt,val[N],tot,L[N],R[N],fa[N];
LL ans;
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;} 
void dfs(int now,int pre){
    L[now]=n+1,R[now]=0;
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=pre){
        dfs(e[i].to,now);
        L[now]=min(L[now],L[e[i].to]),R[now]=max(R[now],R[e[i].to]);
    }
    if(L[now]==n+1)L[now]=R[now]=++tot;
}
struct Eg{
    int u,v,w,id;
    inline bool operator<(const Eg&rhs)const{return w<rhs.w;}
}E[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",val+i);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    dfs(1,0);
    for(int i=1;i<=n;++i)E[i]=(Eg){L[i],R[i]+1,val[i],i};
    sort(E+1,E+n+1);
    for(int i=1;i<=tot+1;++i)fa[i]=i;
    vector<int>vec,vc;
    vec.push_back(1);
    for(int i=2;i<=n+1;++i){
        if(i==n+1||E[i].w!=E[i-1].w){
            for(int id:vec){
                if(find(E[id].u)!=find(E[id].v))vc.push_back(E[id].id);
            }
            for(int id:vec){
                int x=find(E[id].u),y=find(E[id].v);
                if(x!=y)ans+=E[id].w,fa[y]=x;
            }
            vec.clear();
        }
        vec.push_back(i);
    }
    sort(vc.begin(),vc.end());
    printf("%lld %d\n",ans,vc.size());
    for(int i:vc)printf("%d ",i);
    return 0;
}