CF1120D Power Tree 题解
Solution
part 1
对子树操作，自然想到 DFS。但是题目里的操作仅仅是针对叶子节点的，所以用的不是纯粹的 DFS 序。通过这种办法，就能把子树操作转化为序列操作，而每个子树内所有的叶子要对应一个叶子编号的区间。
具体实现时我们只需要维护节点 子树内叶子节点编号的左端点 和右端点 。说明如果控制了 ，能够让我们对 区间内的叶子修改一个值。
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&°[x]==1) l[x]=r[x]=++num; // 叶子，赋值编号 e[++m]=(edge){l[x],r[x]+1,w[x],x}; // 下面会提到这一步}做完了这一步，似乎离解决还很远。
不要忘了本题最开始的目标，无论权值是多少，都能把所有叶子节点的权值变为 0。
这个该怎么入手？我们能做的只有区间加减法，怎么才能做到把权值都变为 0？
如果我们从「终态」去想，就能发现本题的巧妙之处。
一个全 0 序列，它的差分序列也全为 0！
而差分操作是在左端点 修改上一个值，在右端点后一个位置 修改一个值。感性理解，就像是把 的值传递给了 ，如果传递的这个值就是 的权，那么 处将变为 0。这不就是一种无视具体权值，构造出 0 的办法吗？
更进一步的，从 再往后传，一直传达到 的时候，序列就变成了全 0！
差分序列全 0，原序列有两种情况。
- 全 0。显然是正确的。
- 全相等。但是如果我们在区间修改的时候在把这个值去掉，那么最终也还是全 0。
呼之欲出了！
我们之前处理了每个点能控制的区间。能从 修改一个值到 ，不妨看作从 向 连了一条边，再建一个虚拟节点 。
这样，当且仅当这张图连通时，能够把序列变为全 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 longconst 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("");}觉得这篇文章怎么样？
点个赞，让更多人看到！
评论区