21725번 1명이 은행역할하면 된다는 관찰못하고 복잡하게 트리상에서 풀다가 만들어진 문제?
N개의 정점을 가진 트리가 있다.
이중에서 K개의 노드는 특별한 노드로, 특별한 노드 i는 자신을 제외한 다른 모든 노드에게서 a[i]만큼의 돈을 받아야한다.
N번 이하의 송금으로 모든 결제를 완료해라.

//아래는 짜다가 만 코드
#include "core/base.h"
void solve(){
	int n,m; cin>>n>>m;
	Arr<int> p(n),s(n,1),ufs(n,1);
	iota(p.begin(),p.end(),0);
	Arr<Arr<int>> g(n);
	func(int,root,int x){return x==p[x]?x:root(p[x]);};
	Arr<int> pay(n);//현재 그룹상태에서 x가 pay[x]만큼 지불했음
	Arr<int> pay2par(n);//부모에게 송금 (음수는 부모가 자식에게 송금)
	Arr<int> paysum(n);//서브트리 pay합
	Arr<Arr<int>> buf;//x에 지연시킨 merge들
	func(int,precalc,int x){
		paysum[x]=pay[x];
		for(auto y:g[x])
			if(y!=p[x])
				paysum[x]+=precalc(y);
		return paysum[x];
	};
	//x를 루트로
	//부모쪽 서브트리에서 pv만큼 송금요청
	//x쪽 서브트리에선 paysum[x]만큼 송금요청
	func(void,process,int x,int pv){
		//x가 수금해서 처리
		pay2par[x]+=pv*s[x]-paysum[x]*(s[root(x)]-s[x]);
		int ypv=pv+pay[x];
		for(auto y:g[x])
			if(y!=p[x])
				ypv+=paysum[y];
		for(auto y:g[x])
			if(y!=p[x])
				process(y,ypv-paysum[y]);
		pay[x]=0;
	};
	func(void,merge,int x,int y){
		x=root(x),y=root(y);
		if(ufs[x]<ufs[y])
			swap(x,y);
		precalc(y);
		process(y,0);
		
		buf[x].push_back(y);
		p[y]=x;
		ufs[x]+=ufs[y];
	};
	for(int i=0;i<m;i++){
		int z,x,y; cin>>z>>x>>y;
		if(z==1){
			x--,y--;
			merge(x,y);
		}else{
			x--;
			pay[x]+=y/s[root(x)];
		}
	}
	int r=root(0);
	precalc(r);
	process(r,0);
	Arr<tint> ans;
	for(int i=0;i<n;i++)
		if(p[i]!=i){
			if(pay2par[i]<0)
				ans.emplace_back(p[i],i,-pay2par[i]);
			if(pay2par[i]>0)
				ans.emplace_back(i,p[i],pay2par[i]);
		}
	cout<<sz(ans)<<endl;
	for(auto[x,y,z]:ans)
		println(x+1,' ',y+1,' ',z);
}