【浮*光】#树形DP# 树形DP的习题集

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

/*【p2996】拜访奶牛
N(1<=N<=50000)个朋友构成一棵树。求：可以拜访的朋友的最大数目。
限制：对于由一条路直接相连的两个奶牛,只能拜访其中的一个。 */

/*【0/1型树形dp】← 也只有我这样叫...
f[x] 即 拜访x时最大数量，g[x] 即 不拜访x时最大数量。
转移方程：f[x]=1+∑g[son[i]]，g[x]=∑max(f[son[i]],g[son[i]])。
不妨假设从1号点出发，那么答案即为max(f[1],g[1])。 */

void reads(int &x){ //读入优化（正负整数）
    int fa=1;x=0;char s=getchar();
    while(s<‘0‘||s>‘9‘){if(s==‘-‘)fa=-1;s=getchar();}
    while(s>=‘0‘&&s<=‘9‘){x=(x<<3)+(x<<1)+s-‘0‘;s=getchar();}
    x*=fa; //正负号
}

const int N=100019;

int n,f[N],g[N],head[N],tot=0;

struct node{ int ver,nextt; }e[N*2];

void add(int x,int y)
 { e[++tot].ver=y,e[tot].nextt=head[x],head[x]=tot; }

void dp(int x,int fa_){
    f[x]=1; //选择自己
    for(int i=head[x],y;i;i=e[i].nextt){
        if(e[i].ver==fa_) continue; y=e[i].ver;
        dp(y,x); f[x]+=g[y]; //(1),不能选儿子
        g[x]+=max(f[y],g[y]); //(2),不选x,下方随意
    }
}

int main(){
    reads(n); for(int i=1,x,y;i<n;i++)
        reads(x),reads(y),add(x,y),add(y,x);
    dp(1,0); cout<<max(f[1],g[1])<<endl;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

/*【p2585】三色二叉树
递归给出一棵二叉树。每个节点的颜色可以是0,1,2。
要求：父子、兄弟节点的颜色不同。求最多/最少的0色点个数。 */

/*【0/1型树形dp】因为只用考虑0色点的个数，所以每个点可以分为：0色/非0色。
那么就和 模板题p2996 很相似了。f[i]/g[i] 表示 i 为/不为 0色时，以i为根的子树中 0色点的最值个数。
二叉树则：f[i]=1+g[ls[i]]+g[rs[i]],g[i]=min/max(f[ls[i]]+g[rs[i]],g[ls[i]]+f[rs[i]])。 */

void reads(int &x){ //读入优化（正负整数）
    int fa=1;x=0;char s=getchar();
    while(s<‘0‘||s>‘9‘){if(s==‘-‘)fa=-1;s=getchar();}
    while(s>=‘0‘&&s<=‘9‘){x=(x<<3)+(x<<1)+s-‘0‘;s=getchar();}
    x*=fa; //正负号
}

const int N=500019; char ss[N]; int f[N],g[N],ls[N],rs[N],p,n;

void init(){ p++,n++; int now=n;
  if(ss[p]==‘2‘) ls[now]=n+1,init(),rs[now]=n+1,init();
  if(ss[p]==‘1‘) ls[now]=n+1,init(); }

void dp_max(int x){
  if(!x) return; dp_max(ls[x]),dp_max(rs[x]);
  f[x]=1+g[ls[x]]+g[rs[x]], //↓↓ 三个点必须只选一个 
  g[x]=max(f[ls[x]]+g[rs[x]],g[ls[x]]+f[rs[x]]); }

void dp_min(int x){
  if(!x) return; dp_min(ls[x]),dp_min(rs[x]);
  f[x]=1+g[ls[x]]+g[rs[x]], //↓↓ 三个点必须只选一个 
  g[x]=min(f[ls[x]]+g[rs[x]],g[ls[x]]+f[rs[x]]); }

int main(){
    scanf("%s",ss+1),init(); //递归输入
    dp_max(1),printf("%d ",max(f[1],g[1]));
    memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    dp_min(1),printf("%d\n",min(f[1],g[1]));
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

/*【p4107】兔子与樱花 
n个节点的樱花树，0号节点是根节点。第i个节点有c_i朵樱花。
每一个节点都有载重量m。对于节点i，要求：儿子个数son_i<=m-c_i。
要删除一些节点。每次删除之后儿子节点会向上连接。求最多能删除多少节点。*/

/*【树形dp+贪心】每次删除选定节点i后，它父亲fa_增加的重量为(son_i+c_i)-1。
那么就可以把每个节点的权值看成子节点数目+樱花数(son_i+c_i)。
于是就有贪心策略：优先选择权值小的，判断能否去掉，若能去掉则更新当前节点的重量。*/

void reads(int &x){ //读入优化（正负整数）
    int fa=1;x=0;char s=getchar();
    while(s<‘0‘||s>‘9‘){if(s==‘-‘)fa=-1;s=getchar();}
    while(s>=‘0‘&&s<=‘9‘){x=(x<<3)+(x<<1)+s-‘0‘;s=getchar();}
    x*=fa; //正负号
}

const int N=2000019; int n,m,ans=0,c[N]; 

vector<int> son[N]; //存儿子节点 

bool cmp(int a,int b){ return c[a]<c[b]; }

void dp(int x){ //↓↓先递归到最底部，再自底而上一步步贪心
    for(int i=0;i<(int)son[x].size();i++) dp(son[x][i]);
    sort(son[x].begin(),son[x].end(),cmp); //每层都要重新排序
    c[x]+=son[x].size(); //当前节点的权值改成son_i+c_i
    //↑↑因为自底而上，所以不会有冲突和重复，每个节点只会遍历一次
    for(int i=0;i<(int)son[x].size();i++)
     { if(c[x]+c[son[x][i]]-1>m) break; //不能再删除了
       c[x]+=c[son[x][i]]-1,ans++; } //按照贪心策略...
}

int main(){
    reads(n),reads(m); for(int i=1;i<=n;i++) reads(c[i]);
    for(int i=1,k,x;i<=n;i++){ reads(k); //↓↓转化为根节点为1
        while(k--) reads(x),son[i].push_back(x+1);
    } dp(1); printf("%d\n",ans); return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

/*【p3698】小Q的棋盘
求 ‘从0号点出发，移动p步’ 最多能经过多少节点。*/

/*【树形dp+贪心】dfs求出以0为起点的最长一条链，此链上的点只经过一次，消耗1步；
其它的点经过后需要返回这条链上，消耗2步。然后分类讨论：是否能走完链、走完树。*/

void reads(int &x){ //读入优化（正负整数）
    int fa=1;x=0;char s=getchar();
    while(s<‘0‘||s>‘9‘){if(s==‘-‘)fa=-1;s=getchar();}
    while(s>=‘0‘&&s<=‘9‘){x=(x<<3)+(x<<1)+s-‘0‘;s=getchar();}
    x*=fa; //正负号
}

const int N=519; int n,p,max_l=0,x,y;

int head[N],ver[N<<1],nextt[N<<1],tot=0,dep[N];

void add(int x,int y){ ver[++tot]=y,nextt[tot]=head[x],head[x]=tot; }

void dfs(int x,int fa){ for(int i=head[x];i;i=nextt[i])
  if(ver[i]!=fa) dep[ver[i]]=dep[x]+1,dfs(ver[i],x); }

int main(){
    reads(n),reads(p); for(int i=1;i<n;i++) reads(x),reads(y),add(x,y),add(y,x);
    dfs(0,-1); for(int i=1;i<n;i++) if(max_l<dep[i]) max_l=dep[i];
    if(p<=max_l) printf("%d\n",p+1); //比最长链短
    else if(p>=max_l+2*(n-max_l-1)) printf("%d\n",n); //比所有长度还长
    else printf("%d\n",max_l+(p-max_l)/2+1); //只能走除最长链之外的一部分
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

/*【p3478】Station
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大。*/

/*【树形dp】f[x]表示子树x中所有点到点x的距离之和，g[x]表示整个树中所有点到点x的距离之和。
x的子树的对应路径中，有si[to[i]]个点到x的距离比to[i]多1：f[x]=∑(f[to[i]]+si[to[i]])。
可知g[1]=f[1]。因为有n-si[to[i]]个点到to[i]的距离比到x多1，加n-si[to[i]]；
有si[to[i]]个点到to[i]的距离比到x少1，所以再减si[to[i]]；所以g[to[i]]=g[x]+n-2*si[to[i]]。*/

void reads(int &x){ //读入优化（正负整数）
    int fa=1;x=0;char s=getchar();
    while(s<‘0‘||s>‘9‘){if(s==‘-‘)fa=-1;s=getchar();}
    while(s>=‘0‘&&s<=‘9‘){x=(x<<3)+(x<<1)+s-‘0‘;s=getchar();}
    x*=fa; //正负号
}

const int N=1000019; int n,ans=0,f[N],g[N];

int head[N],ver[N<<1],nextt[N<<1],tot=0,siz[N];

void add(int x,int y){ ver[++tot]=y,nextt[tot]=head[x],head[x]=tot; }

void dfs1(int x,int fa){ siz[x]=1; for(int i=head[x];i;i=nextt[i])
  if(ver[i]!=fa) dfs1(ver[i],x),siz[x]+=siz[ver[i]],f[x]+=f[ver[i]]+siz[ver[i]]; }

void dfs2(int x,int fa){ for(int i=head[x];i;i=nextt[i])
  if(ver[i]!=fa) g[ver[i]]=g[x]+n-2*siz[ver[i]],dfs2(ver[i],x); }

int main(){
    reads(n); for(int i=1,x,y;i<n;i++) 
        reads(x),reads(y),add(x,y),add(y,x);
    dfs1(1,0); g[1]=f[1]; dfs2(1,0); //分别求出f[],g[]
    for(int i=1;i<=n;i++) if(g[ans]<g[i]) ans=i; 
    cout<<ans<<endl; return 0; //g[]中最大的就是ans
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

/*【p3478】Station
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大。*/

/*【树形dp】f[x]表示子树x中所有点到点x的距离之和，g[x]表示整个树中所有点到点x的距离之和。
x的子树的对应路径中，有si[to[i]]个点到x的距离比to[i]多1：f[x]=∑(f[to[i]]+si[to[i]])。
可知g[1]=f[1]。因为有n-si[to[i]]个点到to[i]的距离比到x多1，加n-si[to[i]]；
有si[to[i]]个点到to[i]的距离比到x少1，所以再减si[to[i]]；所以g[to[i]]=g[x]+n-2*si[to[i]]。*/

void reads(int &x){ //读入优化（正负整数）
    int fa=1;x=0;char s=getchar();
    while(s<‘0‘||s>‘9‘){if(s==‘-‘)fa=-1;s=getchar();}
    while(s>=‘0‘&&s<=‘9‘){x=(x<<3)+(x<<1)+s-‘0‘;s=getchar();}
    x*=fa; //正负号
}

const int N=1000019; int n,ans=0; ll f[N],g[N],siz[N];

int head[N],ver[N<<1],nextt[N<<1],tot=0;

void add(int x,int y){ ver[++tot]=y,nextt[tot]=head[x],head[x]=tot; }

void dfs1(int x,int fa){ siz[x]=1; for(int i=head[x];i;i=nextt[i])
  if(ver[i]!=fa) dfs1(ver[i],x),siz[x]+=siz[ver[i]],f[x]+=f[ver[i]]+siz[ver[i]]; }

void dfs2(int x,int fa){ for(int i=head[x];i;i=nextt[i])
  if(ver[i]!=fa) g[ver[i]]=g[x]+n-2*siz[ver[i]],dfs2(ver[i],x); }

int main(){
    reads(n); for(int i=1,x,y;i<n;i++) 
        reads(x),reads(y),add(x,y),add(y,x);
    dfs1(1,0); g[1]=f[1]; dfs2(1,0); //分别求出f[],g[]
    for(int i=1;i<=n;i++) if(g[ans]<g[i]) ans=i; 
    cout<<ans<<endl; return 0; //g[]中最大的就是ans
}