USACO P8900题解
涉及算法 贪心+构造 
题目给出的是一根无根树，所以不妨设 1 号为根节点
把每个点的 h_i 减去 av (其中 av =\frac{\sum_{i=1} ^n h_i } {n} ) 用数组 f 储存
对于每个 f_i 都有三种情况
-
f_i=0 无需任何操作
-
f_i<0 需从 i 的父节点索取 -f_i
-
f_i>0 需向 i 的父节点转移 f_i
(为方便表述，以上操作定义为问题 I )
显然每个父节点都与它的子节点相关联，所有 dfs 时应后序遍历
同时更新 h_i 的值，表示在解决了以 i 为根节点的子树的问题 I 后的权值
void dfs1(int u,int fa){
for(auto v:g[u]){
if(v==fa) continue;
dfs1(v,u);
}
f[u]=h[u]-av;
if(fa!=0) h[fa]+=f[u];
}
我们发现在解决问题 I 中的子问题 2 时父节点的权值可能为负
这时我们就需调整转移顺序从 i 的父节点的父节点转移，以此类推
先进行转移操作
如果一个点 v 无法向上 u 转移就意味着它要向上索取
此时操作数应 +1，意味着 u 必须下放 -f_v 给 v
否则的话直接由 v 到 u 转移 f_v 即可
证明：如何保证 u 一定有 -f_v 转移给 v 呢
f_i 维护的是解决了以 i 为根节点的子树的问题 I 后的权值与 av 的差
所以往下转移的这一部分一定是被考虑进去的，如果无法转移的话应由上一层先行下放
void dfs2(int u,int fa){
for(auto v:g[u]){
if(v==fa||f[v]<0) continue;
dfs2(v,u);
}
for(auto v:g[u]){
if(v==fa||f[v]>=0) continue;
ans++;
op[ans]={u,v,-f[v]};
dfs2(v,u);
}
if(f[u]>0&&fa!=0){
ans++;
op[ans]={u,fa,f[u]};
}
}
AC Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
const int M=1e7+5;
int n;
LL ans,f[N],h[N],sum,av;
vector<int> g[N];
struct OP{
int st,ed;
LL num;
}op[M];
void dfs1(int u,int fa){
for(auto v:g[u]){
if(v==fa) continue;
dfs1(v,u);
}
f[u]=h[u]-av;
if(fa!=0) h[fa]+=f[u];
}
void dfs2(int u,int fa){
for(auto v:g[u]){
if(v==fa||f[v]<0) continue;
dfs2(v,u);
}
for(auto v:g[u]){
if(v==fa||f[v]>=0) continue;
ans++;
op[ans]={u,v,-f[v]};
dfs2(v,u);
}
if(f[u]>0&&fa!=0){
ans++;
op[ans]={u,fa,f[u]};
}
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
n=read();
for(int i=1;i<=n;i++){
h[i]=read();
sum+=h[i];
}
for(int i=1;i<n;i++){
int u,v;
u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
av=sum/n;
dfs1(1,0);
dfs2(1,0);
cout<<ans<<'\n';
for(int i=1;i<=ans;i++){
cout<<op[i].st<<" "<<op[i].ed<<" "<<op[i].num<<'\n';
}
}
展示
