88 lines
1.3 KiB
C++
88 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
vector<int> g[200010];
|
||
|
||
long long hay[200010];
|
||
struct node
|
||
{
|
||
int to;
|
||
long long w;
|
||
};
|
||
vector<node> m[200010];
|
||
long long avg = 0;
|
||
int ans = 0;
|
||
int indegree[200010];
|
||
|
||
void dfs(int u, int f) {
|
||
for (int v : g[u]) {
|
||
if (v != f)
|
||
{
|
||
dfs(v, u);
|
||
}
|
||
}
|
||
if(hay[u]==avg)
|
||
return;
|
||
|
||
ans++;
|
||
if (hay[u] > avg) {
|
||
m[u].push_back({f, hay[u] - avg});
|
||
hay[f] += hay[u] - avg;
|
||
indegree[f]++;
|
||
} else {
|
||
hay[f] -= avg-hay[u];
|
||
m[f].push_back({u, avg-hay[u]});
|
||
indegree[u]++;
|
||
}
|
||
}
|
||
|
||
|
||
/*
|
||
首先dfs找到每条边搬多少，然后有个细节是如果直接做可能出现负数，
|
||
所以要再用一个bfs，先从没有入度的点开始走，避免这种情况
|
||
*/
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
scanf("%lld", &hay[i]);
|
||
avg += hay[i];
|
||
}
|
||
|
||
avg /= n;
|
||
for (int i = 1; i < n; i++) {
|
||
int a, b;
|
||
cin>>a>>b;
|
||
g[a].push_back(b);
|
||
g[b].push_back(a);
|
||
}
|
||
|
||
dfs(1, 0);
|
||
cout << ans << endl;
|
||
queue<int> q;
|
||
|
||
for (int i = 1; i <= n; i++)
|
||
{
|
||
if (indegree[i] == 0)
|
||
{
|
||
q.push(i);
|
||
}
|
||
}
|
||
while(q.size()>0)
|
||
{
|
||
int cur=q.front();
|
||
q.pop();
|
||
for(node i:m[cur])
|
||
{
|
||
cout<<cur<<" "<<i.to<<" "<<i.w<<endl;
|
||
indegree[i.to]--;
|
||
if(indegree[i.to]==0)
|
||
{
|
||
q.push(i.to);
|
||
}
|
||
}
|
||
}
|
||
|
||
|
||
}
|