CF566C Logistical Questions

题面传送门
首先拿到这个题马上猜一个结论：如果以重心为根，那么每个父亲的权值不大于任何一个儿子的权值。
考虑证明：对这个权值函数求导得到\(\frac{3}{2}\sqrt n\)可以发现是一个单调递增的函数，二阶导数为\(\frac{3}{4\sqrt n}\)是不增的。
所以如果一个儿子比父亲小，那么它的父亲一定比父亲的父亲小，所以当前根不是重心，矛盾。
所以我们如果求出一个点的答案，并且可以算出每个子树的导数和，那么至多有一颗子树的导数减去剩下的导数为正。
所以每次点分找到重心然后对重心求答案分治即可。时间复杂度\(O(nlogn)\)
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 200000
#define M 500000
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*x+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound 
using namespace std;
int n,m,k,x,y,z,A[N+5],Id,Fl[N+5],Pus,siz[N+5],dp[N+5],We;db W[N+5],ToT,Ans=9e18,Ns,Ps;
struct yyy{int to,w,z;};struct ljb{int head,h[N+5];yyy f[N+5<<1];I void add(int x,int y,int z){f[++head]=(yyy){y,z,h[x]};h[x]=head;}}s;
I int GS(int x,int La){int S=1;yyy tmp;for(RI i=s.h[x];i;i=tmp.z) tmp=s.f[i],!Fl[tmp.to]&&tmp.to^La&&(S+=GS(tmp.to,x));return S;}
I void Make(int x,int La){yyy tmp;siz[x]=1;dp[x]=0;for(RI i=s.h[x];i;i=tmp.z) tmp=s.f[i],!Fl[tmp.to]&&tmp.to^La&&(Make(tmp.to,x),dp[x]=max(dp[x],siz[tmp.to]),siz[x]+=siz[tmp.to]);dp[x]=max(dp[x],Pus-siz[x]);dp[x]Ps&&(Solve(tmp.to,x),0));
}
int main(){
	freopen("1.in","r",stdin);
	RI i;dp[0]=1e9;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i