树形DP新手向教程
内容
刷了一遍大概去年这个时候做的题。。
写在前面
树形DP。树是一种非常优美的数据结构，在上面DP那就更加优美了。
由于树上没有环，在上面直接dfs的效率就是$O(n)$的。这样对于某些在树上的最优化问题，我们可以dfs到叶子上（一般在叶子上的最大最小值都是很显然的），然后回溯的时候更新它的父亲，这就是树形DP的基本思路。
先看一个非常经典的题目：
luogu1352 没有上司的舞会
题目描述
某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入输出格式
输入格式：
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0 0
输出格式：
输出最大的快乐指数。
输入输出样例
输入样例#1：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
输出样例#1：
5
题解
这个题思路是非常直接的，$f[i][0/1]$表示在i点上选还是不选。那么对于树中间的一个节点，$f[i][1]$就等于它所有儿子不选再加自己的权值。假如要不选这个点，$f[i][0]$就等于它所有儿子选和不选中的最大值，也就是：
$$f[i][0]=\sum_{(i,j)\in G}max(f[j][0],f[j][1])$$
$$f[i][1]=v[i]+\sum_{(i,j)\in G}f[j][0]$$
非常的好写啊：
#include <cstdio>
#include <algorithm>
#define N 6010
using namespace std;
struct node
{
int to,next;
}e[N*2];
int tot,st[N];
void add(int x,int y)
{
e[++tot].to=y;
e[tot].next=st[x];
st[x]=tot;
}
int f[N][2],v[N],x,y,n;
void dfs(int now,int pre)
{
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
dfs(e[i].to,now),f[now][1]+=f[e[i].to][0],
f[now][0]+=max(f[e[i].to][0],f[e[i].to][1]);
f[now][1]+=v[now];
}
main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&v[i]);
for (int i=1;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1,-1);
printf("%d",max(f[1][0],f[1][1]));
}
luogu2607 [ZJOI2008]骑士
题目描述
Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
输入输出格式
输入格式：
输入文件knight.in第一行包含一个正整数N，描述骑士团的人数。
接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出格式：
输出文件knight.out应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
输入输出样例
输入样例#1：
3
10 2
20 3
30 1
输出样例#1：
30
说明
对于30%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 100；
对于80%的测试数据，满足N ≤ 10 000。
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
题解
没发现跟上个题很像吗，只是树上有环，而且只有一个。
可以百度下基环树，对于这种树，只需要环断掉一条边，dp完了加上端点两边的贡献就可以了。
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 1000010
using namespace std;
int fun[N],a,b;
long long f[N][2];
struct node
{
int next,to,v;
}e[2000010];
int st[1000010],vis[N],n,s,tot,x1,x2,E;
void add(int x,int y)
{
e[tot].to=y,e[tot].next=st[x],st[x]=tot++;
//e[++tot].to=x,e[tot].v=z,e[tot].next=st[y],st[y]=tot;
}
void find_circle(int x,int pre)
{
vis[x]=1;
for (int i=st[x];~i;i=e[i].next)
{
if ((i^1)==pre) continue;
if (vis[e[i].to])
{
x1=x,x2=e[i].to;
E=i;
continue;
}
find_circle(e[i].to,i);
}
}
void dfs(int x,int pre)
{
f[x][0]=0;
f[x][1]=fun[x];
for (int i=st[x];~i;i=e[i].next)
{
if ((i^1)==pre) continue;
if (i==E || (i^1)==E)
continue;
dfs(e[i].to,i);
f[x][1]+=f[e[i].to][0];
f[x][0]+=max(f[e[i].to][1],f[e[i].to][0]);
}
}
main()
{
memset(st,-1,sizeof st);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a,&b),add(i,b),add(b,i),fun[i]=a;
long long ans=0;
for (int i=1;i<=n;i++)
{
if (vis[i]) continue;
find_circle(i,-2);
dfs(x1,-1);
long long temp=f[x1][0];
dfs(x2,-1);
temp=max(temp,f[x2][0]);
ans+=temp;
}
printf("%lld",ans);
}
接下来两个很像的题。
luogu1270 访问美术馆
题目描述
经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。
输入输出格式
输入格式：
第1行是警察赶到的时间，以s为单位。第2行描述了艺术馆的结构，是一串非负整数，成对地出现：每一对的第一个数是走过一条走廊的时间，第2个数是它末端的藏画数量；如果第2个数是0，那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出，请看样例。
一个展室最多有20幅画。通过每个走廊的时间不超过20s。艺术馆最多有100个展室。警察赶到的时间在10min以内。
输出格式：
输出偷到的画的数量
输入输出样例
输入样例#1：
60
7 0 8 0 3 1 14 2 10 0 12 4 6 2
输出样例#1：
2
题解
设计状态$f[i][j]$表示在i点花j时间最大收益。把路径的时间乘2加到它的下一个节点上。这样的话到叶子节点上就用总时间减去路径时间除五就好了。在普通节点上枚举分给两个叶子节点的时间。数据小随便艹。
#include <cstdio>
#include <algorithm>
using namespace std;
int f[200][700],cnt,tot;
void dfs(int now)
{
int time,num;
scanf("%d%d",&time,&num);
time*=2;
if (!num)
{
int l=++tot,r=++tot;
dfs(l),dfs(r);
for (int i=time;i<=cnt;i++)
for (int j=0;j<=i-time;j++)
f[now][i]=max(f[now][i],f[l][i-j-time]+f[r][j]);
}
else
for (int i=time;i<=cnt;i++)
f[now][i]=min((i-time)/5,num);
}
main()
{
scanf("%d",&cnt),cnt--;
dfs(0);printf("%d\n",f[0][cnt]);
}
luogu3360 偷天换日
题目背景
神偷对艺术馆内的名画垂涎欲滴准备大捞一把。
题目描述
艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就
是分为两个走廊。每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是要耗费时间的。
警察会在n 秒后到达进口，在不被逮捕的情况下你最多能得到的价值。
输入输出格式
输入格式：
第一行一个整数 n(n≤600)。
第二行若干组整数，对于每组整数（t,x），t 表示进入这个展览厅或经过走廊要耗费 t秒的时间，若x>0 表示走廊通向的展览厅内有x 幅画,接下来x对整数(w,c)表示偷一幅价值为 w 的画需要 c秒的时间。若x=0 表示走廊一分为二。(t，c≤5; x≤30)
输入是按深度优先给出的。房间和走廊数不超过 300 个。
输出格式：
仅一个整数，表示能获得的最大价值。
输入输出样例
输入样例#1：
50
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4
输出样例#1：
1500
题解
和上面一样，就是把叶子节点改成背包。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 610
using namespace std;
int f[N][N],cnt,tot;
void dfs(int now)
{
int time,num;
scanf("%d%d",&time,&num);
time*=2;
if (!num)
{
int l=++tot,r=++tot;
dfs(l),dfs(r);
for (int i=time;i<=cnt;i++)
for (int j=0;j<=i-time;j++)
f[now][i]=max(f[now][i],f[l][i-j-time]+f[r][j]);
}
else
{
int t[num+10],v[num+10];
for (int i=1;i<=num;i++)
scanf("%d%d",&v[i],&t[i]);
for (int i=time;i<=cnt;i++)
{
int dp[i+10];memset(dp,0,sizeof dp);
for (int j=1;j<=num;j++)
for (int k=i-time;k>=t[j];k--)
dp[k]=max(dp[k],dp[k-t[j]]+v[j]);
f[now][i]=dp[i-time];
}
}
}
main()
{
scanf("%d",&cnt),cnt--;
dfs(0);printf("%d\n",f[0][cnt]);
}
luogu1131 [ZJOI2007]时态同步
题目描述
小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。
在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激烈电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。
激励电流在导线上的传播是需要花费时间的，对于每条边e，激励电流通过它需要的时间为te，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小Q有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？
输入输出格式
输入格式：
第一行包含一个正整数N，表示电路板中节点的个数。
第二行包含一个整数S，为该电路板的激发器的编号。
接下来N-1行，每行三个整数a , b , t。表示该条导线连接节点a与节点b，且激励电流通过这条导线需要t个单位时间。
输出格式：
仅包含一个整数V，为小Q最少使用的道具次数。
输入输出样例
输入样例#1：
3
1
1 2 1
1 3 3
输出样例#1：
2
说明
对于40%的数据，N ≤ 1000
对于100%的数据，N ≤ 500000
对于所有的数据，te ≤ 1000000
题解
感觉非常贪心的题。每个节点找它子节点最大的时间，其他的加一下。
#include <cstdio>
#include <algorithm>
#define N 500010
using namespace std;
struct node
{
int to,next,v;
}e[N*2];
int tot,st[N],n,s,x,y,z,f[N];
long long ans;
void add(int x,int y,int z)
{
e[++tot].to=y;
e[tot].next=st[x];
e[tot].v=z;
st[x]=tot;
}
void dfs(int now,int pre)
{
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
dfs(e[i].to,now),
f[now]=max(f[now],f[e[i].to]+e[i].v);
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
ans+=f[now]-f[e[i].to]-e[i].v;
}
main()
{
scanf("%d%d",&n,&s);
for (int i=1;i<n;i++)
scanf("%d%d%d",&x,&y,&z),
add(x,y,z),add(y,x,z);
dfs(s,-1);
printf("%lld",ans);
}
luogu1273 有线电视网
题目描述
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
输入输出格式
输入格式：
输入文件的第一行包含两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的结点总数，M为用户终端的数量。
第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。
接下来的N-M行每行表示—个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下：
K A1 C1 A2 C2 … Ak Ck
K表示该转播站下接K个结点(转播站或用户)，每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。
输出格式：
输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。
输入输出样例
输入样例#1：
5 3
2 2 2 5 3
2 3 2 4 3
3 4 2
输出样例#1：
2
题解
$f[i][j]$表示以$i$为根节点的子树中，选择$j$个客户后剩余的金钱。
$f[i][j]=max(f[i][j],f[i][j-k]+f[i’][k]$
然后$i’$是$i$的所有儿子，可以直接枚举。。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 5010
using namespace std;
struct node
{
int to,next,v;
}e[N*2];
int tot,st[N],m,n,s,x,y,z,f[N][N],tmp[N],g[N];
void add(int x,int y,int z)
{
e[++tot].to=y;
e[tot].next=st[x];
e[tot].v=z;
st[x]=tot;
}
void dfs(int now)
{
for (int i=st[now];i;i=e[i].next)
{
dfs(e[i].to);
for(int j=0;j<=g[now];j++)
tmp[j]=f[now][j];
for(int j=0;j<=g[now];j++)
for(int k=1;k<=g[e[i].to];k++)
f[now][k+j]=max(f[now][j+k],tmp[j]+f[e[i].to][k]-e[i].v);
g[now]+=g[e[i].to];
}
}
main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n-m;i++)
{
scanf("%d",&x);
for (int j=1;j<=x;j++)
scanf("%d%d",&y,&z),
add(i,y,z);
}
memset(f,0xaf,sizeof f);
for (int i=n-m+1;i<=n;i++)
scanf("%d",&f[i][1]),g[i]=1;
for (int i=1;i<=n;i++)
f[i][0]=0;
dfs(1);
for(int i=m;i>=0;i--)
if(f[1][i]>=0)
{
printf("%d\n",i);
break;
}
}
胡策的诡异题
一道胡策时搞的题，感觉非常有意思。
我们先dfs一遍，只算出它子树对它做出的贡献。这样的话根算出的就是总的答案。
然后再dfs一遍，从根向下走，先把它父亲的答案减去自己的贡献，算出它父亲另外的儿子对自己做的贡献。然后加上父亲的贡献，再算出子树对自己的贡献加上。具体细节还是看代码。
#include <cstdio>
#define N 2000010
using namespace std;
struct edge
{
int to,next;
}e[N*2];
int st[N],val[N],d[N],n,x,y,tot;
void add(int x,int y)
{
e[++tot].to=y;
e[tot].next=st[x];
st[x]=tot;
}
double f1[N],f2[N];
void dfs(int now,int pre)
{
f1[now]=val[now];
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
d[now]++;
if (pre!=-1)
d[now]++;
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
{
dfs(e[i].to,now);
if (pre!=-1)
f1[now]+=f1[e[i].to]/(double)(d[now]-1);
else
f1[now]+=f1[e[i].to]/(double)d[now];
}
}
void work(int now,int pre)
{
if (pre!=-1)
{
double temp=(f2[pre]-val[pre])*d[pre];
double temp2=temp-f1[now];
double temp3=(f1[now]-val[now])*(d[now]-1);
if (d[pre]>1)
f2[now]=(temp2/(double)(d[pre]-1)+val[pre])/(double)d[now]+temp3/(double)d[now];
else
f2[now]=val[pre]/(double)d[now]+temp3/(double)d[now];
f2[now]+=val[now];
}
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
work(e[i].to,now);
}
main()
{
freopen("walking.in","r",stdin);
freopen("walking.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&val[i]);
for (int i=1;i<n;i++)
scanf("%d%d",&x,&y),
add(x,y),add(y,x);
dfs(1,-1);
// for (int i=1;i<=n;i++)
// printf("%.2lf ",f1[i]);puts("");
f2[1]=f1[1];
work(1,-1);
// for (int i=1;i<=n;i++)
// printf("%.2lf ",f2[i]);puts("");
double maxs=f2[1];int ans=1;
for (int i=1;i<=n;i++)
if (maxs>f2[i])
maxs=f2[i],ans=i;
printf("%d\n",ans);
}
luogu3237 [HNOI2014]米特运输
题目描述
米特是D星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的D星上，这种米特能源的运输和储存一直是一个大问题。
D星上有N个城市，我们将其顺序编号为1到N，1号城市为首都。这N个城市由N-1条单向高速通道连接起来，构成一棵以1号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为0，属于第1层；根结点的子节点深度为1，属于第2层；依此类推，深度为i的结点属于第i+l层。
建好高速通道之后，D星人开始考虑如何具体地储存和传输米特资源。由于发展程度不同，每个城市储存米特的能力不尽相同，其中第i个城市建有一个容量为A[i]的米特储存器。这个米特储存器除了具有储存的功能，还具有自动收集米特的能力。
如果到了晚上六点，有某个储存器处于未满的状态，它就会自动收集大气中蕴含的米特能源，在早上六点之前就能收集满；但是，只有在储存器完全空的状态下启动自动收集程序才是安全的，未满而又非空时启动可能有安全隐患。
早上六点到七点间，根节点城市（1号城市）会将其储存器里的米特消耗殆尽。根节点不会自动搜集米特，它只接受子节点传输来的米特。
早上七点，城市之间启动米特传输过程，传输过程逐层递进：先是第2层节点城市向第1层（根节点城市，即1号城市）传输，直到第1层的储存器满或第2层的储存器全为空；然后是第3层向第2层传输，直到对于第2层的每个节点，其储存器满或其予节点（位于第3层）的储存器全为空；依此类推，直到最后一层传输完成。传输过程一定会在晚上六点前完成。
由于技术原因，运输方案需要满足以下条件：
(1)不能让某个储存器到了晚上六点传输结束时还处于非空但又未满的状态，这个时候储存器仍然会启动自动收集米特的程序，而给已经储存有米特的储存器启动收集程序可能导致危险，也就是说要让储存器到了晚上六点时要么空要么满；
(2)关于首都——即1号城市的特殊情况， 每天早上六点到七点间1号城市中的米特储存器里的米特会自动被消耗殆尽，即运输方案不需要考虑首都的米特怎么运走；
(3)除了1号城市，每个节点必须在其子节点城市向它运输米特之前将这座城市的米特储存器中原本存有的米特全部运出去给父节点，不允许储存器中残存的米特与外来的米特发生混合；
(4)运向某一个城市的若干个来源的米特数量必须完全相同，不然，这些来源不同的米特按不同比例混合之后可能发生危险。
现在D星人已经建立好高速通道，每个城市也有了一定储存容量的米特储存器。为了满足上面的限制条件，可能需要重建一些城市中的米特储存器。你可以，也只能，将某一座城市（包括首都）中屎来存在的米特储存器摧毁，再新建一座任意容量的新的米特储存器，其容量可以是小数（在输入数据中，储存器原始容量是正整数，但重建后可以是小数），不能是负数或零，使得需要被重建的米特储存器的数目尽量少。
输入输出格式
输入格式：
第一行是一个正整数N，表示城市的数目。 接下来N行，每行一个正整数，其中的第i行表示第i个城市原来存在的米特储存器的容量。 再接下来是N-I行，每行两个正整数a，b表示城市b到城市a有一条高速通道(a≠b)。
输出格式：
输出文件仅包含一行，一个整数，表示最少的被重建（即修改储存器容量）的米特储存器的数目。
输入输出样例
输入样例#1：
5
5
4
3
2
1
1 2
1 3
2 4
2 5
输出样例#1：
3
说明
【样例解释】
一个最优解是将A[1]改成8，A[3]改成4，A[5]改成2。这样，2和3运给1的量相等，4和5运
给2的量相等，且每天晚上六点的时候，1，2满，3，4，5空，满足所有限制条件。
对于100%的数据满足N< 500000，A[j] < 10^8
题解
对于树上任一个点，其权值一旦确定，整棵树的权值即可确定。
从根往下推，记下所有点取值的时候根应该取什么值，然后sort一下找最长的相同区间。
数太大了怎么办？hash一下呗
#include <cstdio>
#include <algorithm>
#define N 500010
#define mod 19260817
using namespace std;
typedef long long ll;
int v[N],son[N],bro[N],x,y,du[N],n,ans;
void dfs(int now,int val)
{
v[now]=(ll)v[now]*val%mod;
val=(ll)val*du[now]%mod;
for (int i=son[now];i;i=bro[i])
dfs(i,val);
}
main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&v[i]);
for (int i=1;i<n;i++)
scanf("%d%d",&x,&y),
bro[y]=son[x],son[x]=y,du[x]++;
dfs(1,1);
sort(v+1,v+1+n);
for (int i=1,las;i<=n;i=las)
{
for (las=i+1;las<=n && v[las]==v[i];las++);
ans=max(ans,las-i);
}
printf("%d\n",n-ans);
}