基本树形DP---zoj_3201

?????? http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3201????????

?????? 树形DP，理解了其实很简单，一气呵成！！对于某个节点u，这个节点对于每个子节点都要更新一次，而且在更新时，子节点的信息已经递归的更新完成了。在更新完某一个子节点之后，此时的dp[u]就包含了之前更新的子节点的信息了。（如果之前不知道肯定不知道我在说什么TAT）还要注意的一点就是，针对某个子节点v更新的时候，我们需要的dp[u]是更新v之前的dp值，因此需要逆序更新。。这其实也很好理解。最后分析一下效率，没个子节点更新一次，与边数对应，因此共更新n-1次，没次更新都是n*n,那么总共的效率是

O（n^3）。

??????

#include<cstdio>#include<algorithm>#include<string.h>#include<vector>using namespace std;vector<int> adj[105];int n,ss,w[105],dp[105][105];void solve(int u,int fa){int size=adj[u].size();dp[u][1]=w[u];for(int i=0;i<size;++i){int v=adj[u][i];if(v==fa)continue;solve(v,u);for(int j=n;j>=2;--j){for(int k=1;k<=j;++k){dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);}}}}int main(){while(scanf("%d %d",&n,&ss)!=EOF){memset(adj,0,sizeof(adj));memset(dp,0,sizeof(dp));for(int i=0;i<n;++i)scanf("%d",&w[i]);for(int i=0;i<n-1;++i){int u,v;scanf("%d %d",&u,&v);adj[u].push_back(v);adj[v].push_back(u);}solve(0,-1);int res=0;for(int i=0;i<n;++i)res=max(res,dp[i][ss]);printf("%d\n",res);}}

?

?