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]++;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
|
|||
|
|
/*
|
|||
|
|
<EFBFBD><EFBFBD><EFBFBD><EFBFBD>dfs<EFBFBD>ҵ<EFBFBD>ÿ<EFBFBD><EFBFBD><EFBFBD>߰<EFBFBD><EFBFBD><EFBFBD><EFBFBD>٣<EFBFBD>Ȼ<EFBFBD><EFBFBD><EFBFBD>и<EFBFBD>ϸ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ܳ<EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD>bfs<EFBFBD><EFBFBD><EFBFBD>ȴ<EFBFBD>û<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȵĵ㿪ʼ<EFBFBD>ߣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
*/
|
|||
|
|
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);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
|
|||
|
|
}
|