树形DP中山纪念中学宋新波课件

树形DP中山纪念中学宋新波树形DP中山纪念中学宋新波1例一：最大利润政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。告诉你每个火车站的利润，问你可以获得的最大利润为多少。例如下图是火车站网络：最佳投资方案是在1，2，5，6这4个火车站开饭店可以获得利润为90例一：最大利润政府邀请了你在火车站开饭店，但不允许同时在两个2例一：最大利润输入：第一行输入整数N(<=100000)，表示有N个火车站，分别用1，2。。。，N来编号。接下来N行，每行一个整数表示每个站点的利润，接下来N-1行描述火车站网络，每行两个整数，表示相连接的两个站点。输出：输出一个整数表示可以获得的最大利润。样例输入：样例输出：6901020254030304513342364例一：最大利润输入：第一行输入整数N(<=100000)，表3分析任意两个火车站有且只有一条路径，是一棵树。我们用f[x]表示在以x为根的树中开饭店，x一定要开，所能获得的最大利润，g[x]表示在以x为根的树中开饭店，x一定不开，所能获得的最大利润，如果x开，则它的儿子们y1,…yk一定不能开，如果x不开，它的儿子们可开可不开，于是得到以下状态转移方程：f[x]=+a[x](yi是x的儿子)g[x]=(yi是x的儿子)

实现时用dfs去实现，每个点只需求一次，所以时间复杂度为O(N)。分析任意两个火车站有且只有一条路径，是一棵树。4例二：电子眼【GDKOI2006】东莞市是一个环境优美、气候宜人的城市。因为城市的交通并不繁忙，市内的道路网很稀疏。准确地说，东莞市有N条马路和N个路口，每条马路连接两个路口，每两个路口之间最多只有一条马路。作为一条交通网络，显然每两个路口之间都是可达的。为了更好地管理东莞市的交通，市长决定在一些路口加装电子眼，用来随时监视路面情况。这些装在路口的电子眼能够监视所有连接到这个路口的马路。现在市长想知道最少需要在多少个路口安装电子眼才能监视所有的马路。市长已经把所有的路口都编上了1～N的号码。

给你东莞市的地图，你能帮忙吗？

例二：电子眼【GDKOI2006】东莞市是一个环境优美、气候5例二：电子眼【GDKOI2006】Input输入文件第1行包括一个数字N(1<=N<=100000)，表示路口数。接下来N行，第i+1行的第一个数字ki表示有ki条马路与路口i相连，后面紧跟着ki个数字，表示与路口i直接相连的路口。Output输出最少需要安装电子眼的数量。SampleInput3223213212SampleOutput2

例二：电子眼【GDKOI2006】Input6分析题目给出的模型正好是一棵树加上一条边，所以一定有且仅有一个环去掉环上任意一条边得到树DFS找到环上一条边，设连接x和y什么情况才能去掉呢？X一定要选或者y一定要选就可以了从而得到树形DP模型分析题目给出的模型正好是一棵树加上一条边，所以一定有且仅有一7分析f[x]表示在x处安装电子眼的情况下监控以x为根的子树中所有边所需安装的最少电子眼数G[x]表示在x处不安装电子眼的情况下监控以x为根的子树中所有边所需安装的最少电子眼数f[x]:=min(f[y],g[y])+1,其中y是x的儿子g[x]:=f[y],其中y是x的儿子以x和y为根分别做一次树形DP答案就是min(f[x],f[y]),时间复杂度为O(N)分析f[x]表示在x处安装电子眼的情况下监控以x为根的子树中8例三：选课大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。例三：选课大学里实行学分。每门课程都有一定的学分，学生只要选9例三：选课下面举例说明例子中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。例三：选课下面举例说明10例三：选课输入：输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。输出：输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。例三：选课输入：11分析根据“每门课的直接选修课最多只有一门”这个条件可以知道该题目的模型是由若干棵树构成的森林。如下左边为输入数据，右图为输入数据对应的森林。74220104217176222157346分析根据“每门课的直接选修课最多只有一门”这个条件可以知道该12方法一首先添加一个0号结点，让森林中的所有树根都成为0号结点的儿子，从而把森林转化为一棵树。如下图所示：215734602157346方法一首先添加一个0号结点，让森林中的所有树根都成为0号结点13方法一定义f[i,j]表示在以i为根的子树中选修j门课程所能获得的最大学分。f[i,0]=0;j>0时，考虑以i的每个儿子结点为根的子树中选修几门课程进行状态转移：时间复杂度极高，超时。方法一定义f[i,j]表示在以i为根的子树中选修j门课程所能14方法二方法一之所以超时，是由于“树”，树的儿子数量可能比较多，这样转移花费大量时间，我们可以把树等价转变为二叉树。左儿子右兄弟法：结点的第一个儿子作为左儿子，右兄弟作为右儿子。21573460方法二方法一之所以超时，是由于“树”，树的儿子数量可能比较多15方法二f[i,j]表示在以i为根的子树中选修j门课程能获得的最多学分。根据i选不选分两种情况：1.不选：那i及i的左子树都不能选，全部在i的右子树中选，f[rightson,j];2.选：i选，i的左子树可以选也可以不选，假设左子树选k个，则另外j-1-k在右子树中选，对应的状态为f[leftson,k]+f[rightson,j-1-k];用自顶向下记忆化搜索实现，时间复杂度为O(mn2)。方法二f[i,j]表示在以i为根的子树中选修j门课程能获得的16方法三不需要转变成二叉树。f[i,j]表示在以i为根的子树中选修j门课程能获得的最多学分。方法一的方法采用自顶向下，所以复杂度很高，我们可以考虑用自下向上。fa[i]存储i的父结点，我们把fa[i]的儿子们看作是一个个物品，当我们计算完f[i,j]后把(j,f[i,j])看作是背包中的一个物品，其中j是体积，f[i,j]是价值，用这个物品去更新f[fa[i],k](k>=j)更新的方法跟背包问题一样。程序段如下：fork:=ndowntojdoiff[fa[i],k-j]+f[i,j]>f[fa[i],k]thenf[fa[i],k]:=f[fa[i],k-j]+f[i,j];用BFS得到一个序列，从后往前执行更新。时间复杂度为O(m*n2)。方法三不需要转变成二叉树。17例四：Debug【GDKOI