题意简述

给你一棵有根树，定义叶子为度数为1的点。

你可以以$ w_x \(的代价控制\)x\(点。选择控制之后可以给它的子树里的叶子加
上\)t (t \in Z )$。

你要以最小的总代价使得：另一个人在叶子上任意放数，你都可以把它

们都变成0。

最后输出最小的总代价，以及有多少点可能被控制，以及每个可能被控制的点的编号

思路索引

首先，我们可以把所有的叶子节点按照 dfs序 抽象成一个序列

接下来，我们可以很神奇的发现，每一个点就对应着一个区间这不是废话吗

然后，选择某个区间后，我们就可以对它进行区间加的操作

既然是区间操作，肯定是不方便的，然后就很自然的想到了差分哪里自然了

若点\(x\)对应区间\([l,r]\)，那么，我们控制点x，就等同于在\(l\)处\(+t\),在\(r+1\)处\(-t\)(因此，我们需要虚构出一个新的叶子节点，以保证不会爆掉)

我们观察一下这个序列，发现如果原数组均为0，则差分数组也均为0

所以说，我们可以在\(l\)到\(r+1\)之间连一条边权为\(w_x\)的边，我们可以在这条边的一端加上一个数，而在另一端减去一个相同的数

我们发现，若所有叶子都联通，那么因为差分数组的和为0，所以我们必然能将每一个点都变成0

求一遍最小生成树即可

代码实现

//```

#include<bits/stdc++.h>

#define ll long long

#define now edge[i].v

#define rep(i,l,r) for(int i=l;i<=r;i++)

using namespace std;

const int SZ=2e5+7;

ll ans;

int cnt;

int L,R;

int u,v;

int n,T;

int w[SZ];

int fa[SZ];

int sz[SZ];

bool vis[SZ];

int head[SZ];

bool f[SZ];

int l[SZ],r[SZ];

struct wxp{

    int v,nxt;

}edge[SZ<<1];

struct pb{

    int u,v,w,o;

}E[SZ];

bool cmp(pb p1,pb p2){

    return p1.w<p2.w;

}

int getfa(int x){

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

}

void add(int u,int v){

    edge[++cnt]=(wxp){v,head[u]};

    head[u]=cnt;

}

void dfs(int x){

    sz[x]=1;

    vis[x]=1;

    for(int i=head[x];i;i=edge[i].nxt)

    if(!vis[now]){

        dfs(now);

        sz[x]+=sz[now];

        l[x]=min(l[x],l[now]);

        r[x]=max(r[x],r[now]);

    }

    if(sz[x]==1) l[x]=r[x]=++T;

    E[x]=(pb){l[x],r[x]+1,w[x],x};

}

int main(){

    scanf("%d",&n);

    rep(i,1,n) scanf("%d",&w[i]);

    rep(i,1,n-1){

        scanf("%d%d",&u,&v);

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

    }

    memset(l,0x3f,sizeof(l));

    dfs(1);

    sort(E+1,E+n+1,cmp);

    rep(i,1,T+1) fa[i]=i;

    int sum=0;

    for(L=1;L<=n;L=R+1){

        R=L;

        while(E[R+1].w==E[L].w&&R<n) R++;

        rep(i,L,R){

            u=E[i].u,v=E[i].v;

            if(getfa(u)!=getfa(v)) f[E[i].o]=1,sum++;

        }

        rep(i,L,R){

            u=E[i].u,v=E[i].v;

            if(getfa(u)!=getfa(v)){

                ans+=1ll*E[i].w;

                fa[fa[u]]=fa[v];

            }

        }

    }

    printf("%I64d %d\n",ans,sum);

    rep(i,1,n) if(f[i]) printf("%d ",i);

}