題目鏈接：點擊查看

題目大意：給出一棵樹，現在要求給每條邊賦上 0 ~ n - 1 的值，且不重復，規定每條路徑 ( u , v ) 的權值和為其簡單路徑上的邊權之和，而整棵樹的權值和為 所有簡單路徑的權值和 之和，現在讓我們給每條邊賦值，使得最后樹的權值和最小，輸出最小值

題目分析：一開始以為是構造，被嚇到了，結果補題的時候發現是個簡單貪心，只需要計算一下每條邊出現的次數，按照出現次數貪心賦值就好了，至于如何計算每條邊的出現次數，可以先用樹形dp計算一下每個節點子樹的大小，然后枚舉 n - 1 條邊就能直接計算出出現次數了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>node[N];LL size[N],num[N];void dfs(int u,int fa) {size[u]=1;for(auto v:node[u]){if(v==fa)continue;dfs(v,u);size[u]+=size[v];} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}dfs(1,-1);for(int i=1;i<=n;i++)num[i]=size[i]*(n-size[i]);sort(num+1,num+1+n,greater<LL>());LL ans=0;for(int i=1;i<n;i++)ans+=i*num[i];printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 树上求和(贪心+树形dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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