题目链接
分析
将叶子节点按dfs序重标号后，每次控制操作可以转化为将子树内叶子节点所在区间加（或减）一个数
不难可以想到将叶子区间进行差分
每次对 \(l\) 到 \(r\) 的操作可以转化为将 \(l\) 上的数转移到 \(r+1\) 上
每次操作后差分数组的和不变
将所有点权变为 \(0\) 即为将所有数转移到 最后的叶子节点编号 \(+1\)（记为 \(n+1\)） 上
将所有节点与 \(n+1\) 直接或间接连边即可
将每个原节点转化为从左叶子到右叶子 \(+1\) 的边，边权为 \(w[i]\) ，求最小生成树即可
对于输出答案，将边权相同的边划分成一段，当枚举到段首时，先判断该段中那些边可以加入，并计入答案，再正常进行 &Kruskal& 即可
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=201005;
int n;
struct EDGE{
int l,r,w,id;
}e[N];
bool cmp(EDGE a,EDGE b){
return a.w<b.w;
}
int head[N],ne[N*2],v[N*2],tot=0;
void add(int x,int y){
ne[++tot]=head[x];
head[x]=tot;
v[tot]=y;
}
int de[N],dfn[N],cn=0,dsiz[N],siz[N],df[N],cntt=0,;
//dsiz为子树中叶子节点的数量
//df为连续的叶子节点的编号
void dfs(int u,int fu){
dfn[u]=++cn;siz[u]=1;
if(de[u]==1&&u!=1) dsiz[u]=1,df[dfn[u]]=++cntt;
for(int i=head[u];i;i=ne[i]){
if(v[i]==fu) continue;
dfs(v[i],u);
dsiz[u]+=dsiz[v[i]];
siz[u]+=siz[v[i]];
}
}
int fa[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int ans[N],cnt=0,an=0;
void kr(){
for(int i=1;i<=cn;i++) fa[i]=i;
sort(e+1,e+n+1,cmp);
e[0].w=-1;//有的数据边权为0
for(int i=1;i<=n;i++){
int x=e[i].l,y=e[i].r,id=e[i].id,w=e[i].w;
if(w!=e[i-1].w){//判断权值相同的边是否可能成为答案
for(int l=i;l<=n;l++){
int p=find(e[l].l),q=find(e[l].r);
if(p!=q) ans[++cnt]=e[l].id;
if(e[l+1].w!=e[l].w) break;
}
}
int p=find(x),q=find(y);
if(p==q) continue;
fa[p]=q;
an+=w;
}
}
signed main(){
scanf("%lld", &n);
for(int i=1;i<=n;i++){
scanf("%lld", &e[i].w);
e[i].id=i;
}
for(int i=1;i<n;i++){
int x,y;
scanf("%lld %lld", &x ,&y);
de[x]++;de[y]++;
add(x,y);add(y,x);
}
dfs(1,0);
for(int i=1;i<=n;i++) e[i].r=df[dfn[i]+siz[i]-1]+1,e[i].l=df[dfn[i]+siz[i]-1]-dsiz[i]+1;//建边
kr();
sort(ans+1,ans+cnt+1);
printf("%lld %lld\n", an, cnt);
for(int i=1;i<=cnt;i++) printf("%lld ", ans[i]);
return 0;
}