21725번 1명이 은행역할하면 된다는 관찰못하고 복잡하게 트리상에서 풀다가 만들어진 문제? N개의 정점을 가진 트리가 있다. 이중에서 K개의 노드는 특별한 노드로, 특별한 노드 i는 자신을 제외한 다른 모든 노드에게서 a[i]만큼의 돈을 받아야한다. N번 이하의 송금으로 모든 결제를 완료해라. //아래는 짜다가 만 코드 #include "core/base.h" void solve(){ int n,m; cin>>n>>m; Arr p(n),s(n,1),ufs(n,1); iota(p.begin(),p.end(),0); Arr> g(n); func(int,root,int x){return x==p[x]?x:root(p[x]);}; Arr pay(n);//현재 그룹상태에서 x가 pay[x]만큼 지불했음 Arr pay2par(n);//부모에게 송금 (음수는 부모가 자식에게 송금) Arr paysum(n);//서브트리 pay합 Arr> 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]>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 ans; for(int i=0;i0) ans.emplace_back(i,p[i],pay2par[i]); } cout<