本文用于记录一些做过的树形dp题

一些基础模型

树的最大独立集

设f[u][1/0]f[u][1/0]f[u][1/0]表示点uuu选/不选，以uuu为根的子树中的最大独立集

f[u][0]=∑max{f[v][0],f[v][1]}f[u][0]=\sum max\{f[v][0],f[v][1]\}f[u][0]=∑max{f[v][0],f[v][1]}
f[u][1]=1+∑f[v][0]f[u][1]=1+\sum f[v][0]f[u][1]=1+∑f[v][0]

树的最小点覆盖集

设f[u][1/0]f[u][1/0]f[u][1/0]表示点uuu选/不选，以uuu为根的子树中的最小点覆盖集

f[u][0]=∑f[v][1]f[u][0]=\sum f[v][1]f[u][0]=∑f[v][1]
f[u][1]=1+∑min{f[v][0],f[v][1]}f[u][1]=1+\sum min\{f[v][0],f[v][1]\}f[u][1]=1+∑min{f[v][0],f[v][1]}

树的重心

一些做题技巧

1. 对于断边问题，我们有两种处理思路：一种是把边的贡献放在儿子上，令一种是先断掉所有边然后把边的贡献放在父亲上
2. 多叉树转二叉树——左儿子右兄弟表示法

void Pre(int x){//多叉树转二叉树vis[x]=true;for(int i=1;i<=n;i++)if(!vis[i]&&graph[x][i]){r[i]=l[x];l[x]=i;Pre(i);}return;
}

多叉树转二叉树后的最小可能深度

3. 开动态栈记录祖先
   [IOI2005]Riv 河流

树形背包

void dfs(int u,int fa){//树形背包基本模板siz[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==fa) continue;dfs(v,u);for(int j=0;j<=min(m,siz[u]);j++){for(int k=0;k<=min(m-j,siz[v]);k++){//f[u][j+k] <-- w(f[u][j],f[v][k])}}siz[u]+=siz[v];} 
}

时间复杂度
=∑i∑j,k∈sonisizj×sizk=\sum_i\sum_{j,k\in son_i}siz_j\times siz_k=∑i​∑j,k∈soni​​sizj​×sizk​
=∑i∑j,k∈soni(∑x[x∈subtreej])×(∑y[y∈subtreej])=\sum_i\sum_{j,k\in son_i}(\sum_x[x\in subtree_j])\times(\sum_y[y\in subtree_j])=∑i​∑j,k∈soni​​(∑x​[x∈subtreej​])×(∑y​[y∈subtreej​])
因为LCA(x,y)=iLCA(x,y)=iLCA(x,y)=i，即任何两点只在lcalcalca处有贡献
所以时间复杂度是O(n2)O(n^2)O(n2)的

[CTSC1997]选课

LuoguP1273 有线电视网

[JSOI2008]魔兽地图

换根dp

经典例题：给定一棵树，对于每个点，求该点到与它距离最远的点的距离。
用f[x][0]f[x][0]f[x][0]表示 xxx的子树中 的点到xxx的最远距离，用f[x][1]f[x][1]f[x][1]表示 xxx的子树中 的点到xxx的次远距离，用f[x][2]f[x][2]f[x][2]表示 不在xxx的子树中 的点到xxx的最远距离。
第一次dp求出f[x][0],f[x][1]f[x][0],f[x][1]f[x][0],f[x][1]，第二次dp用父亲的f[fa][0],f[fa][1]f[fa][0],f[fa][1]f[fa][0],f[fa][1]求出儿子的f[x][2]f[x][2]f[x][2]。
最后答案即为 max(f[x][0],f[x][2])max(f[x][0],f[x][2])max(f[x][0],f[x][2])

基环树

虚树

//虚树板子
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
const ll inf=1e14;
int n,q,k,p[N];
int to[N<<1],nxt[N<<1],head[N],cnt=0;
int fa[N][25],dep[N],dfn[N],ind=0;
int st[N],top=0;
bool key[N];
ll d[N],f[N],g[N],siz[N];
ll ans1,ans2,ans3;
struct edge{int v,len;};
vector ge[N];
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 u,int v){to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs1(int u,int f){dfn[u]=++ind;for(int i=1;i<=22;i++){if(dep[u]<(1<int v=to[i];if(v==f) continue;fa[v][0]=u;dep[v]=dep[u]+1;dfs1(v,u);}
}
int LCA(int u,int v){if(dep[u]=0;i--){if(diff&(1<=0;i--){if(fa[u][i]!=fa[v][i]) {u=fa[u][i];v=fa[v][i];}}return fa[u][0];
}
bool cmp(int a,int b){return dfn[a]if(dep[u]>dep[v]) swap(u,v);return dep[v]-dep[u];
}
void add2(int u,int v,int l){if(dep[u]>dep[v]) swap(u,v);ge[u].push_back((edge){v,l}); 
}
inline void insert(int x){if(!top){st[++top]=x;return;}int lca=LCA(st[top],x);while(top>1&&dep[st[top-1]]>dep[lca]){add2(st[top-1],st[top],dist(st[top-1],st[top]));top--;}if(dep[lca]add2(lca,st[top],dist(lca,st[top]));top--;}if(!top||dep[st[top]]siz[u]=key[u];d[u]=g[u]=0; f[u]=key[u]?0:inf;for(int i=0;iint v=ge[u][i].v;int w=ge[u][i].len;dfs2(v);if(siz[u]>0){ans1+=siz[u]*siz[v]*w+siz[v]*d[u]+siz[u]*d[v];ans2=min(ans2,f[u]+w+f[v]);ans3=max(ans3,g[u]+w+g[v]);}d[u]+=d[v]+siz[v]*w;f[u]=min(f[u],w+f[v]);g[u]=max(g[u],w+g[v]);siz[u]+=siz[v];}ge[u].clear();key[u]=0;
}
int main(){n=read();int a,b;for(int i=1;ia=read();b=read();add(a,b);add(b,a);}dfs1(1,0);q=read();while(q--){k=read();for(int i=1;i<=k;i++) p[i]=read();sort(p+1,p+k+1,cmp);if(p[1]!=1) st[top=1]=1;else st[top=0]=0;for(int i=1;i<=k;i++) insert(p[i]),key[p[i]]=1;while(top>1) add2(st[top-1],st[top],dist(st[top-1],st[top])),--top;ans1=0;ans2=inf;ans3=0;dfs2(1);printf("%lld %lld %lld\n",ans1,ans2,ans3);}return 0;
}

树上动态dp

树上最优选点/选边问题

[POI2011] DYN-Dynamite
CF671D 【Roads in Yusland】

• 树上选不相交链问题
  该问题满足最优子结构，即如果要在uuu的子树里面选链，我们可以先对uuu的每一个儿子vvv的子树求出最优解，再在uuu子树的剩余未选择部分里面选链。
  P5021 [NOIP2018 提高组] 赛道修建
  XSY4197 Snow

与树有关的区间dp

f[i][j]f[i][j]f[i][j]表示节点i到节点j构成树的贡献，按照区间长度从小到大的顺序进行区间dp。
[NOIP2003 提高组] 加分二叉树
f[i][j]f[i][j]f[i][j]表示节点i到节点j构成树的最大加分。
二叉树的加分取决于谁是根，于是我们在区间内枚举根kkk来转移：
f[i][i]=a[i]f[i][i]=a[i]f[i][i]=a[i]
f[i][j]=max{f[i][k−1]×f[k+1][j]+f[k][k]}(i≠j)f[i][j]=max\{f[i][k-1]\times f[k+1][j]+f[k][k]\}(i\not=j)f[i][j]=max{f[i][k−1]×f[k+1][j]+f[k][k]}(i​=j)