CF1120D Power Tree 题解

· · 题解

可能更好的阅读体验

题目传送门

题目大意

给定一棵 n 个点的有根树，1 为根。
你可以选择花费 w_u 的代价控制 u 点。当一个点被控制时你可以选择给它的子树内的叶子的点权都加上一个值 v。你需要控制若干个点，使得花费的代价尽量少，无论怎样规定叶子的初始点权，都可以通过操作你选择的点来让所有叶子的点权清空。
你需要输出代价和的最小值以及所有点，满足它存在于某一种最优选择中。

题目解析

显然我们如果按照 dfs 序对所有的叶子节点重标号，那么每一个点都对应的是一个区间。
所以问题就转化成：给定一个序列，现在又 n 个区间，对于一个区间可以花费代价 w_i 然后将这个区间区间加、减任意一个数，使得序列初始值为任何值时，都能清空。

这样就可以联想到一道题：给定一个序列，给出一些区间的和，询问每个给出区间的和是否会与前面的条件矛盾。

其实两道题的解法是类似的。
对于一个区间 [l,r]，操作的代价为 w，如果将整个序列差分那么就相当于在 a_l 加上一个数，然后在 a_{r+1} 减去这个数，显然就转化为图中节点 l,r+1 两个点之间一条边权为 w 的无向边。然后最后的代价就是最小生成树。

这样就转化为求一张图中最小生成树的边权和以及可能在最小生成树里面的边。
前者不难求出吗，主要的问题在于后者。
其实这个问题很简单。我们考虑 Kruskal 的过程。
如果我们当前处理到一条边，我们需要同时考虑边权与这条边相同的边是否能够加到最小生成树里面，如果可以加入就代表这条边可能出现在最小生成树中。统计完之后再依次把这些边能加入的都加入到最小生成树里面去就可以了。

算法复杂度：O(n\log n)

核心代码：

int n,u,v,head[maxn],to[maxn<<1],nex[maxn<<1],w[maxn],kkk;
#define add(x,y) nex[++kkk]=head[x]; head[x]=kkk; to[kkk]=y
int minx[maxn],maxx[maxn],cnt;
void dfs(int x,int pre){
    int i; maxx[x]=-1; minx[x]=INF;
    for(i=head[x];i;i=nex[i]) if(to[i]!=pre){
        dfs(to[i],x); maxx[x]=mmax(maxx[x],maxx[to[i]]); minx[x]=mmin(minx[x],minx[to[i]]);
    } if(maxx[x]==-1) maxx[x]=minx[x]=++cnt; return;
}
struct JTZ{
    int num,l,r,w;
    bool operator < (const JTZ x) const {
        return this->w < x.w;
    }
}e[maxn];
int fa[maxn]; int getfa(int x){ if(fa[x]==x) return x; return fa[x]=getfa(fa[x]); }
int ans[maxn],top; ll sum;
int main(){
    n=read(); int i,j,k; for(i=1;i<=n;i++) w[i]=read();
    for(i=1;i<n;i++){ u=read(); v=read(); add(u,v); add(v,u); }
    dfs(1,-1); for(i=1;i<=n;i++) e[i].num=i,e[i].l=minx[i],e[i].r=maxx[i]+1,e[i].w=w[i];
    sort(e+1,e+n+1); for(i=1;i<=cnt+1;i++) fa[i]=i;
    for(i=1;i<=n;i=j+1){
        j=i; while(e[i].w==e[j+1].w&&j<n) j++;
        for(k=i;k<=j;k++){
            u=getfa(e[k].l); v=getfa(e[k].r);
            if(u!=v) ans[++top]=e[k].num;
        }
        for(k=i;k<=j;k++){
            u=getfa(e[k].l); v=getfa(e[k].r);
            if(u!=v) fa[u]=v,sum+=e[i].w;
        }
    }
    sort(ans+1,ans+top+1);
    print(sum),pc(' '),print(top),pc('\n');
    for(i=1;i<=top;i++) print(ans[i]),pc(" \n"[i==top]);
    return 0;
}