题目链接: http://codeforces.com/contest/1249/problem/F 题意: 一棵树的每个节点有个权值,选择一个节点集,使得任意点对的距离大于$k$ 求最大节点集权值,节点集权值为节点集中节点权值和
题目链接:
http://codeforces.com/contest/1249/problem/F
题意:
一棵树的每个节点有个权值,选择一个节点集,使得任意点对的距离大于$k$
求最大节点集权值,节点集权值为节点集中节点权值和
数据范围:
$1\leq n \leq 200$
$1\leq k \leq 200$
分析:
定义$dp[v][i]$,代表在$v$这颗子树中,被选择的点最小深度恰好是$i$的最大答案
初始状态$dp[v][0]=a[v]$,这是没有子树的情况,然后再逐个添加子树
$ans=max(dp[n][i])$
AC代码:
#include<bits/stdc++.h> #define pii pair<int,int> #define ll long long using namespace std; const int maxn=200+7; int n,m,a[maxn],dp[maxn][maxn],tem[maxn];//dp[i][j]代表在i这个子树中,被选择的点的最小深度是j //ans=max(dp[n][j]) vector<int>ve[maxn]; void dfs(int x,int f){ dp[x][0]=a[x];//dp[x][0]比较特殊,不能通过子树转移 for(int i=0;i<ve[x].size();i++){ int v=ve[x][i]; if(v==f)continue; dfs(v,x); for(int j=0;j<=m;j++)tem[j]=dp[x][j]; for(int j=0;j<=m;j++)//枚举x子树中被用上的最小深度差为j for(int k=0;k<=m;k++)//枚举v子树中被用上的最小深度差为k if(j+k+1>=m)//深度相加合法,也就是可以这么选择 tem[min(j,k+1)]=max(tem[min(j,k+1)],dp[x][j]+dp[v][k]); for(int j=0;j<=m;j++)dp[x][j]=tem[j];//转移完再更新,保证是新子树和原来的子树们更新 } } int main(){ scanf("%d %d",&n,&m); m++; 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); ve[a].push_back(b); ve[b].push_back(a); } dfs(1,-1); int ans=0; for(int i=0;i<=m;i++)ans=max(ans,dp[1][i]); printf("%d\n",ans); return 0; }