[CF348B]Apple Tree _Apple

盛年不重来，一日难再晨，及时当勉励，岁月不待人。这篇文章主要讲述[CF348B]Apple Tree相关的知识，希望能为你提供帮助。
https://www.zybuluo.com/ysner/note/1300249 题面给一棵大小为(n)的树，树的每个叶子节点上有权值。
定义一颗树平衡：对于每一个结点(u)的子树都拥有相同的权值之和。
问至少要减掉多少权值才能使树平衡。

(nleq 10^5)
解析这题想了半天。。。

一开始的想法是(dfs)一遍，回溯时每个点把其所有子树减到其最小子树大小。
然而立即发现我是个**，这会影响子树内的平衡。
如果把一个点的权值定义为它子树内的权值和，
在一个子树内，所有的点都减去同一个值，才不会影响其平衡。
所以如果要在一个点减小其权值，一减就要减它所有儿子权值的(lcm)。
【[CF348B]Apple Tree】为了使当前点平衡，我们需要使其所有子树大小相等。
为了使以后的修改可行，当然要使所有子树大小都为(lcm)的倍数。
如果一个儿子大小小于(lcm)，说明不能保留子树。

#include< iostream> #include< cmath> #include< cstdio> #include< cstdlib> #include< cstring> #include< algorithm> #define ll long long #define re register #define il inline #define pb(a) push_back(a) #define fp(i,a,b) for(re int i=a; i< =b; i++) #define fq(i,a,b) for(re int i=a; i> =b; i--) using namespace std; const int N=1e5+100; int n,m,h[N],cnt,tag=1; ll w[N],ans,sz[N],dp[N],s; struct Edge{int to,nxt; }e[N< < 1]; il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]}; h[u]=cnt; } il int gi() { re int x=0,t=1; re char ch=getchar(); while(ch!=‘-‘& & (ch< ‘0‘||ch> ‘9‘)) ch=getchar(); if(ch==‘-‘) t=-1,ch=getchar(); while(ch> =‘0‘& & ch< =‘9‘) x=x*10+ch-48,ch=getchar(); return x*t; } ll lcm(re ll a,re ll b) { if(a*b> 1e18+5e17) return tag=0,1; return a/__gcd(a,b)*b; } il void dfs(re int u,re int fa) { dp[u]=w[u],sz[u]=1; re int Son=0; for(re int i=h[u]; i+1; i=e[i].nxt) { re int v=e[i].to; if(v==fa) continue; ++Son; dfs(v,u); sz[u]=lcm(sz[u],sz[v]); dp[u]+=dp[v]; } for(re int i=h[u]; i+1; i=e[i].nxt) { re int v=e[i].to; if(v==fa) continue; dp[u]=min(dp[u],dp[v]-dp[v]%sz[u]); } if(!Son) Son=1; dp[u]*=Son; sz[u]*=Son; } int main() { memset(h,-1,sizeof(h)); n=gi(); fp(i,1,n) w[i]=gi(),s+=w[i]; fp(i,1,n-1) { re int u=gi(),v=gi(); add(u,v); add(v,u); } dfs(1,0); printf("%lld ",s-dp[1]); return 0; }