60 pts求调

#include<bits/stdc++.h>
#define For(i,u,G) for(int i=G.head[u];i;i=G.nex[i])
#define int __int128
using namespace std;
#define out(n) putchar(n)
void read(int &x) {
	x=0;
	char y=getchar_unlocked();
	bool flag=0;
	while(y<'0' || y>'9') {
		if(y=='-')flag=1;
		y=getchar_unlocked();
	}
	while((y>='0' && y<='9')) {
		x=(x<<1)+(x<<3)+(y-'0');
		y=getchar_unlocked();
	}
	if(flag)x=-x;
}
void write(int x) {
	if(x<0) {
		putchar('-');
		x=-x;
	}
	if(x<10)putchar(x+'0');
	else {
		write(x/10);
		out(x%10+'0');
	}
}
struct edge{
	int u,v;
};
vector<int>G[400005];
int n,a[200005],u,v,sum,maxid,dp[200005];
bool cmp(int x,int y){
	return dp[x]>dp[y];
}
void dfs1(int u,int fa){
	dp[u]=a[u]-sum;
	int v;
	for(int i=0;i<G[u].size();i++){
		v=G[u][i];
		if(v==fa)continue;
		dfs1(v,u);
		dp[u]+=dp[v];
	}
	sort(G[u].begin(),G[u].end(),cmp);
}
struct ANS{
	int x,y,z;
};
queue<ANS>ans;
void dfs2(int u,int fa){
	int v;
	for(int i=0;i<G[u].size();i++){
		v=G[u][i];
		if(v==fa)continue;
		if(dp[v]==0)continue;
		else if(dp[v]>0){
			dfs2(v,u);
			ans.push({v,u,dp[v]});
		}else{
			ans.push({u,v,-dp[v]});
			dfs2(v,u);
		}
	}
}
signed main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		sum+=a[i];
	}
	for(int i=1;i<n;i++){
		read(u);
		read(v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	sum/=n;
    maxid=rand()%n+1;
	dfs1(maxid,0);
	dfs2(maxid,0);
	write(ans.size());
	while(ans.size()){
		putchar('\n');
		write(ans.front().x);
		putchar(' ');
		write(ans.front().y);
		putchar(' ');
		write(ans.front().z);
		ans.pop();
	}
	return 0;
}
/*
in:
6
3 4 4 5 5 9
1 2
1 4
1 6
3 6
2 5
out:
3
6 3 1
6 1 3
1 2 1

in:
8
1 9 1 13 1 9 1 5
1 2 2 3 2 4 4 8 8 5 4 6 4 7
out:
*/