2011-0031

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by大肥羊

这是一道经典题~~~

题目大意就是有n个部落，你可以在每个部落x建造圣坛，然后获得一定的声望F[x]

对于每一个部落，他都一定和另外一个部落有依赖关系，比如部落x依赖于部落y，如果x和y都建了圣坛，那么你在部落x获得的声望会发生改变，这个变化值为G[x]，题目中会给出，G[x]可能为负，所以有可能会导致部落x的声望暴跌

现在要求一个建造方案使得声望总值最大

这题主要是很难想。。

首先分析题目可以发现根据依赖关系我们可以把部落分割成一个一个的联通块，并且每个联通块里【有且仅有一个环】，如果这一步你想不通的话多画一下图就明白了
也就是说，部落被分成了很多棵树，然后树里面有一个环，就是这个环导致题目难度大增，现在我们就要想办法把环去掉，然后用树形dp来做

想假设环不存在，那么肯定有一个部落没有依赖其他任何部落，于是这个部落就作为根节点来做树形dp，dp的时候用两个参数，dp[x][i],想表示部落下标，i为0表示这个部落不造圣坛，i为1表示部落造圣坛，然后做树形dp转移就行了

但现在由于环的存在，使得总根节点指向了树里的其中一个节点k，所以我们在树形dp的时候就要把环拆掉，再加一个参数j，dp[x][i][j]，x和i的意思同上，j为0表示总根节点依赖的部落不造圣坛，j为1表示总根节点依赖的部落造圣坛，这样就不再有环存在了

by大肥羊

这是一道经典题~~~

题目大意就是有n个部落，你可以在每个部落x建造圣坛，然后获得一定的声望F[x]

对于每一个部落，他都一定和另外一个部落有依赖关系，比如部落x依赖于部落y，如果x和y都建了圣坛，那么你在部落x获得的声望会发生改变，这个变化值为G[x]，题目中会给出，G[x]可能为负，所以有可能会导致部落x的声望暴跌

现在要求一个建造方案使得声望总值最大

这题主要是很难想。。

首先分析题目可以发现根据依赖关系我们可以把部落分割成一个一个的联通块，并且每个联通块里【有且仅有一个环】，如果这一步你想不通的话多画一下图就明白了

也就是说，部落被分成了很多棵树，然后树里面有一个环，就是这个环导致题目难度大增，现在我们就要想办法把环去掉，然后用树形dp来做

想假设环不存在，那么肯定有一个部落没有依赖其他任何部落，于是这个部落就作为根节点来做树形dp，dp的时候用两个参数，dp[x][i],想表示部落下标，i为0表示这个部落不造圣坛，i为1表示部落造圣坛，然后做树形dp转移就行了

但现在由于环的存在，使得总根节点指向了树里的其中一个节点k，所以我们在树形dp的时候就要把环拆掉，再加一个参数j，dp[x][i][j]，x和i的意思同上，j为0表示总根节点依赖的部落不造圣坛，j为1表示总根节点依赖的部落造圣坛，这样就不再有环存在了