网站建设数据表设计 性别,广告联盟wordpress,广告公司手机网站模板,零售电商平台有哪些正题 题目大意
一棵树#xff0c;每个叶子节点有权值#xff0c;每个点的权值是它这棵子树中的所有叶子节点权值之和。可以减少叶子节点的值#xff0c;要求减少最少的值使得对于每个点#xff0c;它的所有子节点的权值都相等。 解题思路
如果将叶子节点的深度优先访问顺…正题 题目大意
一棵树每个叶子节点有权值每个点的权值是它这棵子树中的所有叶子节点权值之和。可以减少叶子节点的值要求减少最少的值使得对于每个点它的所有子节点的权值都相等。 解题思路
如果将叶子节点的深度优先访问顺序排好那么就是一个序列。对于这个序列我们只可以区间减少。那么我们可以先将一个区间减到满足要求再考虑更大的区间。 对于每个点我们先不考虑原本权值。我们对于每个点我们构建一种系数xxx。 对于第iii个点如果它的子树已经平衡了那么当我们将总值减去xix_ixi的倍数时它还是平衡的。 明显这个系数为limxLCM(wsonx)lim_xLCM(w_{son_x})limxLCM(wsonx) 然后这个点的 wxmin{wsonx}∗son_numxmin{wsonx}∗son_numx%limxw_xmin\{w_{son_x}\}*son\_num_xmin\{w_{son_x}\}*son\_num_x\% lim_xwxmin{wsonx}∗son_numxmin{wsonx}∗son_numx%limx codecodecode
#includecstdio
#includevector
#includealgorithm
#define ll long long
#define lcm(x,y) x*y/__gcd(x,y)
using namespace std;
const ll N100010;
vectorint a[N];
ll n,x,y,w[N],ans,size[N],lim[N];
void dp(ll x)
{lim[x]1;if(w[x]) return;ll minw1e18,sum0;for(ll i0;ia[x].size();i){ll ya[x][i];dp(y);lim[x]lcm(lim[x],lim[y]);minwmin(minw,w[y]);sumw[y];}lim[x]*a[x].size();w[x]minw*a[x].size()-minw*a[x].size()%lim[x];anssum-w[x];
}
int main()
{//freopen(pylon.in,r,stdin);//freopen(pylon.out,w,stdout);scanf(%lld,n);for(ll i1;in;i)scanf(%lld,w[i]);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);a[x].push_back(y);}dp(1);printf(%lld,ans);
}
