题目：https://blog.csdn.net/weixin_44584560/article/details/86599565
https://blog.csdn.net/dcx2001/article/details/78269908@##@@@
这类问题主要是统计子树和，通过加减一些子树满足题目中要求的某些性质。
例如：
1.codeforces 767C Garland
这道题是让你把树分成3部分，使每部分点权和相等，这就是通过算子树的size[]实现的。
2.洛谷1122最大子树和
这道题让你剪去一些子树，让剩下的子树点权和最大。这题就要维护子树的点权和，f[i]表示i这颗子树的点权和最大值。
1、codeforce garland
分割一棵树
分成三部分，每部分的和一样
//codeforce 的题，超时了？？？？
//分割一棵树
//分成三部分，每部分的和一样
int summ=0,tot=0;
int w[maxn]; //暖度
int to[maxn*2],fi[maxn],ne[maxn*2];
void link(int x,int y){
to[++tot]=y;
ne[tot]=fi[x];
fi[x]=tot;
}
int n,root,sz[maxn],ans[5],cnt;
void dfs(int x,int fa){ //开始分割，要有fa是因为这是一棵无根树
sz[x]=w[x];
for(int i=fi[x];i;i=ne[i]){
int v=to[i];
if(v!=fa){
dfs(v,x);
sz[x]+=sz[v]; //加上子树的值
}
}
if(sz[x]==summ) {
ans[++cnt]=x;
sz[x]=0;
}
}
int main(){
int x,y;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&x,&y);
if(x!=0){
link(x,i);
link(i,x);
}
else root=i;
w[i]=y;
summ+=y;
}
if(summ%3!=0){
printf("-1\n");
return 0;
}
summ/=3;
dfs(root,0);
if(cnt<=2) {
printf("-1\n");
}
else printf("%d %d\n",ans[2],ans[1]);
return 0;
}
2、P1122 洛谷 最大子树和
是一个很标准的树形DP，上面的第二类：求在树上选一些点满足价值最大的问题
这题是一个比较常见的树型dp的模型（稍有变形）：子树型，给一棵 n 个点的树，以 1 号点为根，求以每个点为根的子树大小
先设立状态： f[u] 表示以u为根且包含u的最大权联通块
状态转移方程：f[u]+=max(0,f[v]); (v为u的孩子) 有些儿子比较丑，美丽指数小于0，可能不选，所以与0作个比较
状态转移比较容易，主要基于dfs实现，还是要多做题才能熟练
int fi[maxn],to[maxn*2],nex[maxn*2];
int n,tot;
void link(int x,int y){
to[++tot]=y;
nex[tot]=fi[x];
fi[x]=tot;
}
int dp[maxn],w[maxn];
int cut[maxn]; //记录要不要剪掉，如果这支树为负的话，就剪掉
int maxx=-1;
void dfs(int x,int fa){
dp[x]=w[x]; //先赋值
for(int i=fi[x];i;i=nex[i]){
int t=to[i];
if(t!=fa) dfs(t,x);
}
for(int i=fi[x];i;i=nex[i]){
int t=to[i];
if(t!=fa&&!cut[t]) dp[x]+=dp[t]; //因为后面递归的时候会自己判断
}
if(dp[x]<0) cut[x]=1;
maxx=max(maxx,dp[x]);
}
int main(){
int x,y;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=n-1;i++){
scanf("%d %d",&x,&y);
link(x,y);
link(y,x);
}
dfs(1,1);
printf("%d\n",maxx);
return 0;
}
这类问题就是让你求在树上选一些点满足价值最大的问题，一般都可以设f[i][j]表示i这颗子树选j个点的最优解。
1.洛谷1272重建道路
这道题是让你剪去最少的边实现最后剩P个点。所以P个点就是背包，剪去的边数就是价值。这题需要转化一下把剪边变成加边。
2.洛谷1273有线电视网
这道题是让你在保证不亏损的情况下满足更多的客户看到转播。此时用户的个数就是容量，f[i][j]表示i这颗子树选j个用户能赚的最多的钱。
1、P1272 洛谷 道路重建
讲解：https://www.luogu.com.cn/problemnew/solution/P1272
int n,num,p;
/*
每个状态代表一棵子树，这个子树与父节点相连。 那么初始化的话dp[i][1]=son[i],一开始都是不连儿子只连父亲
那么转移的那个就变成了dp[u][j]=max(dp[u][j-k]+dp[v][k]-1)
为什么减1呢，因为注意到我们一开始点都是不与儿子相连的，我们通过dp的过程一步一步把他们连起来。
那么对于u->v这个边，一开始在初始化u的时候已经被减掉了，因为他是连接儿子的边，而v->u这个边并没有，因为这个连向父亲的边，
我们要通过v转移，就得用u->v这个边，所以就得补回来。
而且最终算的时候，除了根节点无父亲外，其他的都要和父节点断开，也就是边数+1
第二种就是dp[i][j]表示以i为根的子树，保留j个节点，且当前子树不与父节点相连，需要拆掉的最小边数。
那么我们的初始化就变成了dp[i][1]=deg[i]
也就是把与i相连的所有边全部拆掉。
*/
struct node{
int to;
int next;
}edge[maxn*2];
int head[maxn];
void link(int x,int y){
edge[++num].next=head[x];
edge[num].to=y;
head[x]=num;
}
int dp[maxn][maxn]; //这个的含义是以i为根的子树，保留j个节点，且当前子树不与父节点相连，需要拆掉的最小边数。
int in[maxn]; //给个结点的度
void dfs(int x,int fa){
dp[x][1]=in[x];
for(int i=head[x];i;i=edge[i].next){
if(edge[i].to!=fa){
dfs(edge[i].to,x);
for(int j=p;j>0;j--){
for(int k=1;k<j;k++)
dp[x][j]=min(dp[x][j],dp[x][k]+dp[edge[i].to][j-k]-2); //为甚么减2
//因为再两个in[]里面都加了
}
}
}
}
int main(){
scanf("%d %d",&n,&p);
int x,y;
for(int i=1;i<n;i++){
scanf("%d %d",&x,&y);
in[x]++;
in[y]++;
link(x,y);
link(y,x);
}
memset(dp,0x3f,sizeof(dp));
dfs(1,0);
int ans=INF;
for(int i=1;i<=n;i++) ans=min(ans,dp[i][p]);
printf("%d\n",ans);
return 0;
}
1.明确dp[i][j]含义，表示i节点，选j个用户，能得到的钱的最大值，然后对每个节点做分组背包。
2.怎么看出是分组背包？首先，背包的总容量相当于该点为根节点的子树中所有的用户数量（dp[i][j]的 j 不可能超过它连接的所有用户数）。然后，把该节点的每个儿子看成一组，每组中的元素为选一个，选两个...选n个用户。
3.转移方程 dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-这条边的花费) i,j不解释了，v表示枚举到这一组（即i的儿子），k表示枚举到这组中的元素：选k个用户。
4.最后输出dp[1][i]>=0的i的最大值，所以反向枚举。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;//n为整个有线电视网的结点总数，m为用户终端的数量
//第一个转播站即树的根结点编号为1，其他的转播站编号为2到n-m，用户终端编号为n-m+1到n
int head[3010],k;
int val[3010];//用户为观看比赛而准备支付的钱数
int dp[3010][3010];//dp[i][j]表示i节点，选j个用户，能得到的钱的最大值
struct node
{
int to,next,w;
}edge[10000010];
void adde(int u,int v,int w)
{
edge[++k].to=v; edge[k].next=head[u];
edge[k].w=w; head[u]=k;
}
int dfs(int u)
{
if(u>n-m)//u为用户终端
{
dp[u][1]=val[u];
return 1;
}
int sum=0,t;
for(int k=head[u];k;k=edge[k].next)//该点连接了几个节点意为有几组，遍历每一组
{
int v=edge[k].to;
t=dfs(v); sum+=t; //t为该组的元素个数，或是说这个儿子为根的子树大小（这里的大小指子树中用户的个数），sum为该节点最多可以选多少个用户，即背包容量
for(int j=sum;j>0;j--)
{
for(int i=1;i<=t;i++)//遍历组中的元素，选多少个用户相当于一个元素
{
if(j-i>=0) dp[u][j]=max(dp[u][j],dp[u][j-i]+dp[v][i]-edge[k].w);
}
}
}
return sum;
}
int main()
{
memset(dp,~0x3f,sizeof(dp));//初始化一个极大负值，因为dp可能为负
scanf("%d%d",&n,&m);
for(int u=1;u<=n-m;u++)
{
int size,v,w;
scanf("%d",&size);
for(int j=1;j<=size;j++)
{
scanf("%d%d",&v,&w);
adde(u,v,w);
}
}
for(int i=n-m+1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<=n;i++) dp[i][0]=0;//选0个用户的花费肯定是0啦
dfs(1);
for (int i=m;i>=1;i--)
if (dp[1][i]>=0)
{
printf("%d",i);
break;
}
return 0;
}
这类问题是父亲与孩子有联系的题。基本有两种出法：1.选父亲必须不能选孩子（强制）2.选父亲可以不用选孩子（不强制）。
1.洛谷2458 [SDOI2006]保安站岗
这题就属于类型2.这就需要预估，要不要选这个节点的父亲。f[i][0]表示选自己，f[i][1]表示选孩子，f[i][2]表示选父亲。
2.UVA 1220 Party at Hali-Bula（这是最大独立集问题，用做和上面题区分）
这题就是强制要求父亲和孩子不能同时选，但这题没有要求必须把所有点完全覆盖，只是让选尽可能多的点，所以这样就可以用f[i][0]表示选自己，f[i][1]表示选孩子,省去f[i][2]表示选父亲了，因为没有都覆盖的强制要求，他的父亲选不选可以到他父亲再判断。
1、hdu Anniversary party 1520
选父不选子 不选父则都可以
using namespace std;
const int maxn=1010;
//没过
const int INF=0x3fffffff;
//树形dp
//选父不选子 不选父则都可以
int dp[6010][2]; //0位不选，为选
vector<int> tree[6010];
int w[6010];
int n;
int fa[6010];
void dfs(int t){
dp[t][0]=0;
dp[t][1]=w[t]; //先初始化
for(int i=0;i<tree[t].size();i++){
int son=tree[t][i];
dfs(son); //先递归
dp[t][0]+=max(dp[son][0],dp[son][1]);
dp[t][1]+=dp[son][0];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
fa[i]=-1;
tree[i].clear();
}
int x,y;
// memset(dp,0,sizeof(dp));
while(scanf("%d %d",&x,&y)){
if(x==0&&y==0) break;
fa[x]=y;
tree[y].push_back(x);
}
int root=1;
while(fa[root]!=-1){
root=fa[root];
}
dfs(root);
printf("%d\n",max(dp[root][0],dp[root][1]));
return 0;
}
这类问题就是给你一个条件，问你有多少个点的集合满足这样的条件。这类题主要运用乘法原理，控制一个点不动，看他能做多少贡献。
1. 51nod1588幸运树。 问有多少个三元组满足幸运数字， 可以控制一个点不动，分成子树内，子树外两个部分，分别相乘就行了。
这种题只能根据题目分析，然后随机应变了。
1.洛谷3621 [APIO2007]风铃
把题目中的要求变成公式就行了。
2. 51nod1673树有几多愁
这道题是非常强的综合题，用到了虚树+状压dp+树形dp。
3.51nod1531树上的博弈
非常强的一道博弈题。需要分情况的讨论
2、hdu Computer 2196
对每个点，求距离它最远的点
/*
while(scanf("%d",&n)){
inti();
dfs1(1);
dp[1][2]=0; //根到上面的距离是0
dfs2(1);
for(int i=1;i<=n;i++) printf("%d\n",max(dp[i][0],dp[i][2])); //两个方向，要么是
}
*/
//下面的会超时。。。虽然好理解
/*
struct node{
int id;
int cost; //到爸爸的距离
};
vector<node> tree[maxn];
int dp[maxn][3];
//0代表到子树的最长距离，1代表到子树的次长距离，2代表从i往上走的最短距离
int n;
void inti(){
for(int i=1;i<=n;i++) tree[i].clear();
int x,co;
memset(dp,0,sizeof(dp));
for(int i=2;i<=n;i++){
scanf("%d %d",&x,&co);
node temp;
temp.id=i;
temp.cost=co;
tree[x].push_back(temp);
}
}
void dfs1(int fa){
//最长距离，次长距离
int one=0,two=0;
for(int i=0;i<tree[fa].size();i++){
node child=tree[fa][i];
dfs1(child.id); //先递归
int cost=child.cost+dp[child.id][0];
if(cost>=one){
two=one;
one=+cost;
}
else if(cost>two) two=cost;
}
dp[fa][0]=one;
dp[fa][1]=two;
}
void dfs2(int fa){ //先处理父节点，在处理子节点，所以处理顺序是从上到下，所以最后递归
for(int i=0;i<tree[fa].size();i++){
node temp=tree[fa][i];
if(dp[temp.id][0]+temp.cost==dp[fa][0]){
dp[temp.id][2]=max(dp[fa][2],dp[fa][1])+temp.cost; //如果再最长的路上，那么就加上次长的距离
}
else
dp[temp.id][2]=max(dp[fa][2],dp[fa][0])+temp.cost;
dfs2(temp.id);
}
}
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10000+200;
struct edge
{
int to;//终端点
int next;//下一条同样起点的边号
int w;//权值
} edges[MAXN*2];
int tot;//总边数
int head[MAXN];//head[u]=i表示以u为起点的所有边中的第一条边是 i号边
void add_edge(int u,int v,int w)//添加从u->v，权值为w的边
{
edges[tot].to=v;
edges[tot].w=w;
edges[tot].next = head[u];
head[u] = tot++;
}
int dist[MAXN][3];//dist[i][0,1,2]分别为正向最大距离，正向次大距离，反向最大距离
int longest[MAXN];
int dfs1(int u,int fa)//返回u的正向最大距离
{
if(dist[u][0]>=0)return dist[u][0]; //记忆化
dist[u][0]=dist[u][1]=dist[u][2]=longest[u]=0; //递归边界
for(int e=head[u]; e!=-1; e=edges[e].next)
{
int v= edges[e].to;
if(v==fa)continue;
if(dist[u][0]<dfs1(v,u)+edges[e].w) //更新最长
{
longest[u]=v;
dist[u][1] = max(dist[u][1] , dist[u][0]);
dist[u][0]=dfs1(v,u)+edges[e].w;
}
//更新次长
else if( dist[u][1]< dfs1(v,u)+edges[e].w )//这里一定要记得，要不然无情WA
dist[u][1] = max(dist[u][1] , dfs1(v,u)+edges[e].w);
}
return dist[u][0];
}
void dfs2(int u,int fa)
{
for(int e=head[u];e!=-1;e=edges[e].next)
{
int v = edges[e].to;
if(v==fa)continue;
if(v==longest[u]) dist[v][2] = max(dist[u][2],dist[u][1])+edges[e].w; //如果在最长的一条上
else dist[v][2] = max(dist[u][2],dist[u][0])+edges[e].w; //不在最长的
dfs2(v,u); //后递归
}
}
int main()
{
int n;
while(scanf("%d",&n)==1&&n)
{
tot=0;
memset(dist,-1,sizeof(dist));
memset(head,-1,sizeof(head));
memset(longest,-1,sizeof(longest));
for(int i=2; i<=n; i++)
{
int v,w;
scanf("%d%d",&v,&w);
add_edge(i,v,w);//加边
add_edge(v,i,w);//加边
}
dfs1(1,-1);
dfs2(1,-1);
for(int i=1;i<=n;i++)
printf("%d\n",max(dist[i][0],dist[i][2]));
}
return 0;
}
原文：https://www.cnblogs.com/shirlybaby/p/12319687.html