正題

---

題目大意

一棵樹，每個葉子節點有權值，每個點的權值是它這棵子樹中的所有葉子節點權值之和。可以減少葉子節點的值，要求減少最少的值使得對于每個點，它的所有子節點的權值都相等。

---

解題思路

如果將葉子節點的深度優先訪問順序排好，那么就是一個序列。對于這個序列，我們只可以區間減少。那么我們可以先將一個區間減到滿足要求，再考慮更大的區間。
對于每個點我們先不考慮原本權值。我們對于每個點我們構建一種系數$x$。
對于第$i$個點，如果它的子樹已經平衡了，那么當我們將總值減去$x_i$的倍數時它還是平衡的。
明顯這個系數為$$li{m}_x=LCM(w_{so{n}_x})$$
然后這個點的
$$w_x=min\{w_{so{n}_x}\}?son\_nu{m}_x+min\{w_{so{n}_x}\}?son\_nu{m}_x\%li{m}_x$$

---

$code$

#include<cstdio> #include<vector> #include<algorithm> #define ll long long #define lcm(x,y) x*y/__gcd(x,y) using namespace std; const ll N=100010; vector<int> 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 minw=1e18,sum=0;for(ll i=0;i<a[x].size();i++){ll y=a[x][i];dp(y);lim[x]=lcm(lim[x],lim[y]);minw=min(minw,w[y]);sum+=w[y];}lim[x]*=a[x].size();w[x]=minw*a[x].size()-minw*a[x].size()%lim[x];ans+=sum-w[x]; } int main() {//freopen("pylon.in","r",stdin);//freopen("pylon.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);a[x].push_back(y);}dp(1);printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的jzoj3519-灵能矩阵【LCM,树形dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。