题意有一棵 $n(\le 100004)$ 个点的树，从根节点出发。节点 $x$ 能放梅花，仅当其所有子节点 $y$ 上都放了 $w_y$ 朵梅花。对于 $\forall i\in [1,n]$ ，如果要在 $i$ 上放 $w_i$ 朵梅花，则至少需要在过程中准备多少梅花？题解可以发现对于节点 $x$ ，一定是按某种顺序遍历所有子节点 $y$ 放上梅花，而且不同的顺序得到的答案也不相同。考虑...
题意有 $n(\le 100)$ 个软件可以安装，每个软件会占 $w_i$ 的磁盘空间，价值为 $v_i$ ，每个软件都有至多一个依赖。剩余磁盘空间为 $m(\le 500)$ ，问安装软件的价值最大值。题解环上的软件必须要全装才有收益，所以先缩点。然后把 $0$ 看成树根，并将它与无依赖的软件连边。剩下的就是标准的树形背包问题，只是注意当前枚举的软件一定会安装，否则无法安装子树上的软件。#...
DarkBzoj提交地址题意有 $N(\le 2000)$ 个农民, 他们住在 $N$ 个不同的村子里. 这 $N$ 个村子形成一棵树。每个农民初始时获得 $X$ 的钱。每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民。对于每个农民给定一个值 $v_i$, 求：最少需要多少次操作, 使得每个农民最终拿到的钱 $\geq$ 给定的值。题解有个结论：每条边最...
DarkBzoj提交地址：因为没有SPJ，所以需要特殊处理答案如下：if (ans) printf("%.10f",ans);
else puts("0");题意某个公司有 $n(\le 5\times 10^5)$ 个人, 上下级关系构成了一个有根树，其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒...
题意在一棵 $N$ 个点的树上放 $K$ 个监听器，每个监听器可以监听与它直接相连的节点，但不能监听自己。要求所有节点都被监听，求方案数。$N\le 100000 \ , \ K\le 100$ 。题解真·毒瘤题目。用 $f[x][i][0/1][0/1]$ 表示以 $x$ 节点为根的子树中除了 $x$ 都被监听了，放了 $i$ 个监听器，$x$ 上放没放监听器，$x$ 有没有被监听到 的方...
题意将一棵 $N$ 个点的树上 $K$ 个点染黑，另外的点染白。求黑点两两之间距离和加上白点两两之间距离和的最大值。$N,K\le 2000$ 。题解考虑每一条边的贡献，即为 边权 $\times ($ 一侧的黑点个数 $\times$ 另一侧的黑点个数 $+$ 一侧的白点个数 $\times$ 另一侧的白点个数 $)$ 。用 $f[x][i]$ 表示以 $x$ 为根的子树，黑点有 $i$ ...
庆祝第100篇文章完成！题意一棵有边权的树，有的节点是转播站，有的节点是用户节点。要让用户看到电视，代价为根节点到当前用户节点的路径和，重复的路径不重新计算。每个用户可以支付一定的钱。求在不亏本的情况下，最多可以让多少个用户看到电视。其中点数 $N\le 3000$ 。题解树上背包的裸题。用 $f[x][i]$ 表示在以 $x$ 节点为根的子树中选 $i$ 个用户的最大收益。转移方程式为：$...
题意在树上放一些山贼集团的分部，每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点，如果它被多个分部收保护费，就可能产生收益或损失。求最优的放置方法，可以得到最大利润。其中点数 $N\le 100$ ，分部个数 $P\le 12$ 。题解看到 $P$ 的范围，显然可以对节点上放置分部的状态进行状压。因为每个分部收取的...
题意求所有在树上直径的节点。点数 $N\le 200000$ 。题解我百度谷歌搜了一圈硬是没看到一个像样的题解，去提交记录里面看代码读懂的方法。先跑第一遍 $dfs$ ，记录以 $x$ 为根的子树中深度的最大值 $mx[x]$ 和次大值 $mx2[x]$ ，两者相加再 $+1$ 即为这个子树的直径。然后再跑一遍，对于每个节点 $x$ ，遍历所有子节点 $y$ ，并对子节点向上最大深度 $up...
题意一棵无根树，要求根节点到每个叶子的路径上都至少有一个有色节点。给出根节点到每个叶子节点路径上最后一个有色节点的颜色，求有色节点个数最小值。其中点数 $N\le 1000$ ，叶子节点个数 $M\le 5021$ 。（我按个人习惯反过来了）题解树形dp，用 $f[x][0/1]$ 表示以 $x$ 为根的子树，最后一个有色节点颜色为黑/白的最优情况。考虑状态转移，如果子节点和自己要求一样，则...
时隔半年再来做发现还是不会，于是乎还是写个总结吧。题意一棵二叉树，只能保留 $Q$ 条边，求剩下的边最大边权和。其中点数 $N\le 100$ ，$Q\le 100$ 。题解用 $f[x][j]$ 表示在以 $x$ 为根的子树上保留 $j$ 条边的最优情况。搜索时枚举 $x$ 的子节点 $y$ ，然后类比背包枚举以 $y$ 为根的子树保留的边数 $k$ ，得到状态转移如下：$f[x][j]=...
又是一道我看了题解才知道怎么做的题，我还是太弱了。题意每个骑士都有一个自己痛恨的骑士（不会恨自己），这俩不能在一起，每个骑士有个能力值，问怎么组合使总的能力值最大。其中骑士的人数 $N\le 10^{6}$ 。题解分（看）析（题）题（解）目可以发现，如果将每个关系之间连一个双向边，每个连通块都有且仅有一个环，所以整个图就是一个基环森林，然后拆一条边分成两棵树各跑一遍树形dp即可。拆开看以后也...
重题，双倍经验。https://llf0703.com/p/uva-1292.html而且uva的题还有多组输出，删掉就行了。struct Edge{
int next,to;
} edge[3005];
int head[1505],n,m,a,b,c,cnt,f[1505][2],out[1505];
inline void add(int u,int v)
{
edg...
跟舞会那道题差不多，如果父节点没有取那么所有子节点都必须取；如果父节点取了，子节点取或不取皆可。$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$需要注意的是题目中已经把子树说明了，这就意味着只能有一个点作为根节点，所以应该连单向边，并且事先找到那个点作为根节点。st...
大水题，题意就跟题目名一样，决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ，显然要当前子树和要大于0我们才会取，然后dfs即可。方程式：$$f[x]+=max(f[y],0)$$struct Edge{
int next,to;
} edge[32005];
int s[16005],n,m,a,b,c,cnt,head[16005],w[16005],ans;
inli...