CF1120D Power Tree（构造题，差分，最小生成树）

很有趣的一道题。

首先可以对每个叶子进行编号。按照DFS到的顺序即可。（假设从 $1$ 到 $k$）

然后对每个点求出它管辖的所有叶子的编号。因为是DFS序所以这一定是个区间。设点 $u$ 的这个区间是 $[l_u,r_u]$。

区间加操作，考虑差分，那么每个点的操作就变成了 $l_u$ 加一个数，$r_u+1$ 减一个数。（此时也要考虑 $k+1$）

那么题目要求就变成了所有数都变成 $0$。

感受一下，把 $(l_u,r_u+1,c_u)$ 看做一条带权边，那么当且仅当选择的边构成连通图时满足要求。

那么就变成最小生成树了。

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

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

struct edge{

    int u,v,w,id;

    bool operator<(const edge &e)const{

        return w<e.w;

    }

}e[maxn];

int n,c[maxn],el,head[maxn],to[maxn*],nxt[maxn*],el2;

int lft[maxn],rig[maxn],dfn[maxn],dfs_clock,ccc,fa[maxn],at[maxn],sss[maxn],al;

bool good[maxn];

ll ans;

inline void add(int u,int v){

    to[++el]=v;nxt[el]=head[u];head[u]=el;

}

int getfa(int x){

    return x==fa[x]?x:fa[x]=getfa(fa[x]);

}

void dfs(int u,int f){

    dfn[u]=++dfs_clock;

    lft[u]=n+;rig[u]=;

    for(int i=head[u];i;i=nxt[i]){

        int v=to[i];

        if(v==f) continue;

        dfs(v,u);

        lft[u]=min(lft[u],lft[v]);

        rig[u]=max(rig[u],rig[v]);

    }

    if(!rig[u]) lft[u]=rig[u]=++ccc;

}

int main(){

    n=read();

    FOR(i,,n) c[i]=read();

    FOR(i,,n-){

        int u=read(),v=read();

        add(u,v);add(v,u);

    }

    dfs(,);

    FOR(i,,n) e[++el2]=(edge){lft[i],rig[i]+,c[i],i};

    sort(e+,e+el2+);

    FOR(i,,ccc) fa[i]=i;

    FOR(i,,el2){

        int j=i;

        while(j<=el2 && e[j].w==e[i].w) j++;

        j--;

        FOR(k,i,j){

            int u=e[k].u,v=e[k].v;

            u=getfa(u);v=getfa(v);

            if(u!=v) good[e[k].id]=true,al++;

        }

        FOR(k,i,j){

            int u=e[k].u,v=e[k].v;

            u=getfa(u);v=getfa(v);

            if(u!=v) fa[u]=v,ans+=e[k].w;

        }

        i=j;

    }

    cout<<ans<<" "<<al<<endl;

    FOR(i,,n) if(good[i]) printf("%d ",i);

}