树形dp 学习笔记---（1.19~1.20日志）
made by llj(Jellily)_______________________
标签：树形dp
---
推荐blog
树相关算法（一）——二叉树的遍历、树的重心、树的直径
基本的dp方程
选择节点类
dp[i][0]=dp[j][1]
dp[i][1]=max/min(dp[j][0],dp[j][1])树形背包类
dp[v][k]=dp[u][k]+val
dp[u][k]=max(dp[u][k],dp[v][k−1])例题1
选课
选择一门课，必须要先学会它的必修课，所以这就形成了一种依赖行为，那么他又说要选择的价值最大，这就要用到树形背包的知识了。
//设dp[i][j]表示选择以i为根的子树中j个节点,u代表当前根节点，tot代表其选择的节点的总额。
void dfs(int u,int tot)
{
for(int i=head[x];~i;i=e[i].next)
{
int v=e[i].v;
for(int k=0;k<tot;k++)//这里k从0开始到tot-1，因为v的子树可以选择的节点是u的子树的节点数减一
dp[v][k]=dp[u][k]+val[u];
dfs(v,tot-1)
for(int k=1;k<=tot;k++)
dp[u][k]=max(dp[u][k],dp[v][k-1]);//这里是把子树的值赋给了根节点，因为u选择k个点v只能选择k-1个点。
}
}AC code
#include<bits/stdc++.h>
using namespace std;
const int maxn=305;
int n,m,cnt;
int score[maxn],fa[maxn],f[maxn][maxn],head[maxn];
struct Edge {
int to,next;
}e[maxn<<1];
void add(int from, int to)
{
e[++cnt].to=to;
e[cnt].next=head[from];
head[from]=cnt;
}
void dfs(int u)
{
f[u][1]=score[u];
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
dfs(v);
for(int j=m;j>=1;j--)//倒序枚举体积
for(int k=j-1;k>=1;k--)//枚举物品(可正可倒着枚举)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
//f[u][j]:第u棵子树前i个节点，选了j个的最优值
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for (int i=1;i<=n;i++)
{
scanf("%d%d",&fa[i],&score[i]);
add(fa[i],i);//由父节点指向子节点的单向边
}
m++; //由于0号节点的参与，m需要自加1
dfs(0);
printf("%d",f[0][m]);
return 0;
}例题2
没有上司的舞会
----------
#include<bits/stdc++.h>
using namespace std;
const int maxn=6005;
int n,rt,cnt;
int rd[maxn],R[maxn],head[maxn],f[maxn][7];//rd用来找根,R是快乐值
struct Edge{
int nxt,to;
}e[maxn];
int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
void add(int a,int b)
{
e[++cnt].nxt=head[a];
e[cnt].to=b;
head[a]=cnt;
}
void dfs(int u)
{
f[u][1]=R[u];
for(int i=head[u];~i;i=e[i].nxt)
{
int v=e[i].to;
dfs(v);
f[u][0]+=max(f[v][1],f[v][0]);
f[u][1]+=f[v][0];
}
}
int main()
{
memset(head,-1,sizeof(head));
n=read();
for(int i=1;i<=n;i++)
R[i]=read();
for(int i=1;i<=n;i++)
{
int x=read(),y=read();
rd[x]++;
if(x!=0&&y!=0)add(y,x);
}
for(int i=1;i<=n;i++)
if(rd[i]==0)rt=i;//i无上司，则i为根
dfs(rt);
printf("%d",max(f[rt][0],f[rt][1]));
return 0;
}例题3
最大子树和
这道题的dp方程有变，因为你的操作是切掉这个点，所以你的子树要么加上价值，要么价值为0，所以dp方程是
dp[u]+=max(dp[v],0)
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
int n,a[maxn],head[maxn],h,f[maxn],ans;
struct edge{
int next,to;
}e[maxn];
void add(int x,int y)
{
e[++h].next=head[x];
e[h].to=y;
head[x]=h;
}
void dfs(int u,int fa)
{
f[u]=a[u];
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa)
{
dfs(v,u);
f[u]+=max(0,f[v]);
}
}
ans=max(ans,f[u]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
printf("%d",ans);
}例题3
士兵守卫
题意:选择最少的点来覆盖一棵树，可以用最小点覆盖（也就是二分图最大匹配）或者树形dp来做，
复习vector~~
#include<bits/stdc++.h>
using namespace std;
const int maxn=1500+5;
int f[maxn][9],n;
vector<int>g[maxn];
void add(int x,int y)
{
g[x].push_back(y);
}
void dp(int u,int fa)
{
f[u][0]=0;f[u][10]=1;
for (int i=0;i<g[u].size();i++)//vector是从0开始的！
{
int v=g[u][i];
if (v==fa)continue;
dp(v,u);
f[u][0]+=f[v][11];
f[u][12]+=min(f[v][0],f[v][13]);//选择节点类转移方程
}
}
void work()
{
int x,y,t;
while(scanf("%d",&n)!=EOF)
{
for (int i=0;i<n;i++)g[i].clear();
for (int i=0;i<n;i++)
{
scanf("%d:(%d)",&x,&t);//令人心动的读入方式
for(int i=0;i<t;i++)
{
scanf("%d",&y);
add(x,y);
add(y,x);
}
}
dp(0,-1);
printf("%d\n",min(f[0][0],f[0][14]));
}
}
int main()
{
work();
return 0;
}