树形dp
树形动归一般是依赖于dfs的，根据动归的后效性，父节点的状态一般都依赖子节点的状态以某种方式转移而来
换根的p2015
[设f[i][j]表示i的子树上保留j条边最多苹果数\
f[i][j]=max(f[i][j],f[left][j]+e[left].apple+f[right][k-j]+e[right].apple)\
e[i].apple表示i条树枝的苹果数
]
p2279
[状态表示f[x][0]:覆盖到x的爷爷和x整棵子树（向上2层），最少个数\
f[x][1]:覆盖到x的父亲和x子树(向上一层)\
f[x][2]:覆盖到x整颗子树(向上0层)\
f[x][3]:覆盖x的儿子及其子树(向上-1层)\
f[x][4]:覆盖所有x的孙子及其子树(向上-2层)\
显然f[x][i]一定包含f[x][i+1],y.z是x的儿子\
f[x][0]=1+sum f[y][4](因为i可以覆盖到向上2层，所以它自己必须是消防站~显然)\
x的儿子中有一个一定覆盖的爷爷，同时覆盖到兄弟（因为y一定是选了），其他的儿子只需要覆盖的自己的儿子即可\f[x][1]=min(f[y][0]+sum f[z][3](y!=z))\
f[x][2]=min(f[y][1]+sum[z][2])有一个儿子覆盖到父亲，但无法覆盖到y的兄弟，所以其他儿子要覆盖到自己\
f[x][3]=sum f[y][2]让每个儿子覆盖到自己即可\
f[x][4]=sum f[y][3]让每个儿子覆盖到自己的儿子\
]
P1122 最大子树和
[设f[i][0]为被当前这个点保安控制的点\
显然f[i][0]=sum min(f[son[i]][0],f[son[i]][1],f[son[i][2])+val[i]\
f[i][1]为被当前这个点的儿子控制的点\
显然f[i][1]=sum min(f[son[i][0],f[son[i]][1])如果选择的全部都是f[son[i]][1],\要再加上min(f[son[i]][0]-f[son[i]][1])\
f[i][2]为被当前这个点的fa控制的点\
这个有点麻烦f[i][2]=sum min(f[son[i]][0],f[son[i]][1])我们不妨这样理解，对于i节点我们让它\的父亲节点fa覆盖它，那么根据我们的状态设计，此时必须要满足以i的儿子son[i]为根的子树\之中所有点已经被覆盖那么这时就转化为一个子问题，要让y子树满足条件，只有两种决策：要么son[i]\被son[i]的儿子覆盖，要么被son[i]自己覆盖（即选择son[i]节点）\，只需要在son[i]的这两种状态取min累加就可以了
]
对于(f[i][1])的转移,luogu大佬有详细解释:（这位大佬）(\_\_\_new2zy\_\_\_)
我们可以这样理解，此时既然要保证x点是被自己的儿子覆盖的，那么如果此时y子树已经满足了全部被覆盖，但是y此时被覆盖的状态却是通过y节点自己的儿子达到的，那么x就没有被儿子y覆盖到，那么我们不妨推广一下，如果x所有的儿子y所做的决策都不是通过选择y点来满足条件，那么我们就必须要选择x的一个子节点y，其中y满足(f[y][0]-f[y][1])最小，并把这个最小的差值累加到(f[x][1])中去，这样才能使得x点被自己的儿子覆盖**，状态(f[x][1])也才能合理地得到转移
就是这样1代表选了该点,0没选，假设问号为根节点,0为枝条,1为叶子,这样显然不行,所以取最小花费的点，加入到花费，明白了吧
?
0 0 0 0
1 1 1 1
//代码哥哥：
#include<cstdio>
#define maxn 1520
#define int long long
using namespace std;
inline int min(int a,int b){return a<b?a:b;}
inline int read(){
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
struct edge{
int to,next;
}e[maxn<<1];
int n,tot=0,head[maxn<<1],val[maxn];
int f[maxn][4];
inline void add(int x,int y)//加边
{
tot++;
e[tot].next=head[x];
head[x]=tot;
e[tot].to=y;
}
inline int treedp(int u,int fa){
f[u][0] = val[u];
int sum = 0,mincost = 0x777777f;
for(int i = head[u];i;i=e[i].next){
int y=e[i].to;
if(y==fa) continue;
treedp(y,u);
int az = min(f[y][0],f[y][1]);
f[u][0] += min(f[y][2],az);
f[u][2] += az;
if(f[y][0]<f[y][1]) sum++;//如果选择儿子节点更优,选上,计数器sum++，证明选过f[y][0]
else mincost=min(mincost,f[y][0]-f[y][1]);
f[u][1] += az;
}
if(!sum)f[u][1] += mincost;
}
signed main(){
n=read();
for(int i=1;i<=n;i++)
{
int x=read();
val[x]=read();
int num=read();
while(num>0)
{
int y=read();
add(x,y);
add(y,x);
num--;
}
}
treedp(1,0);
printf("%d",min(f[1][0],f[1][1]));
}
换根dp一般分为三个步骤
1、先指定一个根节点
2、一次dfs统计子树内的节点对当前节点的贡献
3、一次dfs统计父亲节点对当前节点的贡献并合并统计最终答案
二次扫描与换根法:
(f[i]表示以u为根的树的深度和,size[i]表示以i为根子树的结点个数)
(f[v]=f[u]-size[x]+n-size[x]=f[u]+n-2*size[x])
本来是以u为根的树，变成以儿子v为根的树，
那么v的所有结点的深度都会减1，深度和就会减少size[v]，
同样地，所有不在v的子树上的结点的深度都会+1，深度和就会加上n - size[v]，