part 1

对子树操作，自然想到 DFS。但是题目里的操作仅仅是针对叶子节点的，所以用的不是纯粹的 DFS 序。通过这种办法，就能把子树操作转化为序列操作，而每个子树内所有的叶子要对应一个叶子编号的区间。

具体实现时我们只需要维护节点 \(x\) 子树内叶子节点编号的左端点 \(l_x\) 和右端点 \(r_x\)。说明如果控制了 \(x\)，能够让我们对 \([l_x,r_x]\) 区间内的叶子修改一个值。

void dfs(int x,int fa) {	
	l[x]=n+1, r[x]=0; // 初值
	for(int i=h[x];i;i=nxt[i]) {
		int y=ver[i];
		if(y==fa) continue;
		dfs(y,x);
		l[x]=min(l[x],l[y]), r[x]=max(r[x],r[y]);
        // 维护最左和最右编号
	}
	if(x!=1&&deg[x]==1) l[x]=r[x]=++num; // 叶子，赋值编号
	e[++m]=(edge){l[x],r[x]+1,w[x],x}; // 下面会提到这一步
}

做完了这一步，似乎离解决还很远。

不要忘了本题最开始的目标，无论权值是多少，都能把所有叶子节点的权值变为 0。

这个该怎么入手？我们能做的只有区间加减法，怎么才能做到把权值都变为 0？

如果我们从「终态」去想，就能发现本题的巧妙之处。

一个全 0 序列，它的差分序列也全为 0！

而差分操作是在左端点 \(l\) 修改上一个值，在右端点后一个位置 \(r+1\) 修改一个值。感性理解，就像是把 \(l\) 的值传递给了 \(r+1\)，如果传递的这个值就是 \(l\) 的权，那么 \(l\) 处将变为 0。这不就是一种无视具体权值，构造出 0 的办法吗？

更进一步的，从 \(r+1\) 再往后传，一直传达到 \(n+1\) 的时候，序列就变成了全 0！

差分序列全 0，原序列有两种情况。

1. 全 0。显然是正确的。
2. 全相等。但是如果我们在区间修改的时候在把这个值去掉，那么最终也还是全 0。

呼之欲出了！

我们之前处理了每个点能控制的区间。能从 \(l_x\) 修改一个值到 \(r_x+1\)，不妨看作从 \(l_x\) 向 \(r_x+1\) 连了一条边，再建一个虚拟节点 \(n+1\)。

这样，当且仅当这张图连通时，能够把序列变为全 0。而当且仅当选择的边组成其最小生成树时，代价最小！

part 2

事情到这还没完。如果仔细看题面的话，就会发现他让输出的是最优解种可能的最小权值，可能的节点数以及可能的点。

转化一下，就是最优解的并集。

有不同最优解，当且仅当最小生成树不唯一，也就是有相同边权。

解决这个问题，我们只要再 Kruskal 算法里，分别处理权值相同的边，相当于缩成一个“点”。具体看注释。

void kruskal() {
	ll ans=0;
	sort(e+1,e+m+1);
	for(int i=1;i<=num+1;++i) f[i]=i;
	for(int i=1;i<=m;++i) {
		int j=i;
		while(j<m&&e[i].z==e[j+1].z) ++j;
        // 如果有权相等的边，那么这些边都可能在最小生成树里。为什么是可能？如果不连通的话就不在了
        // 所以下面根据连通与否来分别统计，跑两遍是因为如果一边合并一边统计就会导致错误
		for(int k=i;k<=j;++k) {
			int x=e[k].x, y=e[k].y;
			x=get(x), y=get(y);
			if(x!=y) { ++t, v[e[k].id]=1; }
		}
        // 统计可能在最优解中的点，这里的点指的原来的图中的点
		for(int k=i;k<=j;++k) {
			int x=e[k].x, y=e[k].y;
			x=get(x), y=get(y);
			if(x!=y) { f[x]=y, ans+=e[k].z; }
		}
        // 合并[i,j]这些点，正常统计边权
		i=j;
	}
	printf("%lld %d\n",ans,t);
}

最后按照v数组输出就行了。

剩下的代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N=2e5+5;
int n, num, m, t, w[N], l[N], r[N], deg[N], f[N];
int cnt, h[N], ver[N<<1], nxt[N<<1]; 
bool v[N];
struct edge { int x, y, z, id; } e[N<<1];
bool operator<(edge a,edge b) {
	return a.z<b.z;
}
void add(int x,int y) { ver[++cnt]=y, nxt[cnt]=h[x], h[x]=cnt; }
int get(int x) { return f[x]==x? x:f[x]=get(f[x]); }
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	for(int i=1,x,y;i<n;++i) {
		scanf("%d%d",&x,&y);
		add(x,y), add(y,x), ++deg[x], ++deg[y];
	}
	dfs(1,0);
	kruskal();
	for(int i=1;i<=n;++i) if(v[i]) printf("%d ",i);
	puts("");
}