傳送門

文章目錄

• 題意：
• 思路：

題意：

$n\le 200$

思路：

明顯的樹形$dp$，所以考慮一下$dp$狀態。
這個題狀態挺神的。。可能是因為我太菜了，看了半天才看懂。

算法$1$:
復雜度$O(n^3)$

定義$f[i][j]$為以$j$為根的子樹中，選出來的最小深度$\ge j$的最大價值子集，注意這個深度是以$i$為根的子樹的深度，每個子樹從$0$開始，這個狀態就挺繞的，可以稍微理解一下。
直接求$\ge j$的不好求，我們可以先求$=j$的情況，讓后取一個后綴最大值即可。
可以分以下兩種情況考慮：
$(1)$考慮$j=0$的情況，我們可以得到$$f[i][0]=a[i]+\sum _{u是i的兒子}f[u][k]$$
稍微解釋一下，由于要求任意兩點距離$>k$，所以距離兒子為$k$的點再加上兒子到父親的$1$的距離正好是$\ge k+1$，所以直接轉移即可。
$(2)$考慮$j>=1$的情況，我們可以得到$$f[i][j]=max(f[i][j],ma{x}_{x是i的兒子}(f[x][j?1]+\sum _{y是i的兒子且y!=x}f[y][max(i?1,k?i)]))$$
解釋一下$max(i?1,k?i)$兩個的含義，$i?1$是保證了深度至少為$i?1$，$k?i$保證了兩點之間距離$>k$，因為$x$到根為$i$，$y$到根必須$>=k?i+1$，那個$1$正好是$y$到$i$的距離，所以是$k?i$。

復雜度是$O(n^3)$，這里很容易就認為是$O(n^4)$，但是實際上是$O(n^3)$的，因為$dfs$只是遍歷的所有的點，比如下面的代碼：

int cnt=0;for(auto u:ver) {for(auto x:children[u]) {for(auto y:children[u]) {cnt++;}}}

這個代碼是$n^2$的，因為$cnt$的個數$\le n^2$，最外面那層就是我們這里的$dfs$。

// Problem: F. Maximum Weight Subset // Contest: Codeforces - Codeforces Round #595 (Div. 3) // URL: https://codeforces.com/contest/1249/problem/F // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=210,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,k; int a[N]; vector<int>v[N]; LL f[N][N];void dfs(int u,int fa) {LL sum=0; f[u][0]=a[u];for(auto x:v[u]) {if(x==fa) continue;dfs(x,u);f[u][0]+=f[x][k];}for(int i=1;i<n;i++) {for(auto x:v[u]) {if(x==fa) continue;sum=f[x][i-1];for(auto y:v[u]) {if(y==x||y==fa) continue;sum+=f[y][max(i-1,k-i)];}f[u][i]=max(f[u][i],sum);}}for(int i=n-1;i>=0;i--) f[u][i]=max(f[u][i],f[u][i+1]); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);cin>>n>>k;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n-1;i++) {int a,b; scanf("%d%d",&a,&b);v[a].pb(b); v[b].pb(a);}dfs(1,0);printf("%lld\n",f[1][0]);return 0; } /**/

總結

以上是生活随笔為你收集整理的Codeforces Round #595 (Div. 3) F. Maximum Weight Subset 树形dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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