正題

做法就是設$f[i]$表示i的子樹的答案，$sum[i]$為$i$的（子樹的邊權和+i到父親的邊權）$?2$，$sz[i]$表示$i$子樹的的大小。
那么若給$x$的子樹一個遍歷順序$a$，那么就有：$$f[i]=\sum _{i=1}^{so{n}_i}f[a_i]+(\sum _{j=1}^{i?1}sum[a_j])sz[a_i]$$
發現前面這個$f$是固定的，可以不用管。
對于后面的東西若$\frac{sum[a_i]}{sz[a_i]}>\frac{sum[a_{i+1}]}{sz[a_{i+1}}$，那么更換兩個位置產生的上面式子的差值就是$sum[a_{i+1}]sz[a_i]?sum[a_i]sz[a_{i+1}]<0$比原先代價要小。，更換了更優，那么就是按照$\frac{sum[x]}{sz[x]}$來排序。

#include<bits/stdc++.h> using namespace std;const int N=100010; struct edge{int y,nex,c; }s[N<<1]; struct node{long long d;int t;bool operator<(const node q)const{return d*q.t<t*q.d;} }; long long f[N],sum[N]; int sz[N]; int first[N],len=0,n;void ins(int x,int y,int c){s[++len]=(edge){y,first[x],c};first[x]=len; }void dfs(int x,int fa){vector<node> V;sz[x]=1;for(int i=first[x];i!=0;i=s[i].nex) if(s[i].y!=fa){dfs(s[i].y,x);f[x]+=s[i].c*sz[s[i].y]+f[s[i].y],sz[x]+=sz[s[i].y],sum[x]+=2*s[i].c+sum[s[i].y];V.push_back((node){sum[s[i].y]+2*s[i].c,sz[s[i].y]});}sort(V.begin(),V.end());long long S=0;for(int i=0;i<V.size();i++) f[x]+=S*V[i].t,S+=V[i].d; }int main(){scanf("%d",&n);int x,y,c;for(int i=1;i<n;i++)scanf("%d %d %d",&x,&y,&c),ins(x,y,c),ins(y,x,c);dfs(1,0);printf("%lld\n",f[1]); }

總結

以上是生活随笔為你收集整理的城堡迷阵，51nod1527，贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

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