一篇为了纪念一个人而写的题解

# SDOI2008 山贼集团

# 题目描述

某山贼集团在绿荫村拥有强大的势力。整个绿荫村由 $n$ 个连通的小村落组成，并且保证对于每两个小村落有且仅有一条简单路径相连。将小村落从 $1$ 至 $n$ 编号，山贼集团的总部设在编号为 $1$ 的小村落中。

山贼集团除了老大坐镇总部以外，其他的 $p$ 个部门希望在村落的其他地方（洛谷注：其实也包括总部）建立分部。 $p$ 个分部可以在同一个小村落中建设，也可以分别建设在不同的小村落中，在不同的村落建设不同的分部需要花费不同的费用。

每个分部到总部的路径称为这个部门的管辖范围，于是这 $p$ 个分部的管辖范围可能重叠，或者完全相同。当多个分部管辖同一个村落时，他们之间可能发生矛盾，从而损失一部分利益，也可能相互合作，从而获取一部分利益。

请注意，如果相同的分部同时管辖多个村落，那么对于每个村落，都会计算一次收益损失 / 获取。

现在请你编写一个程序，确定 $p$ 个分部的位置，使得山贼集团能够获得最大的收益。

# 输入格式

输入的第一行有两个整数，分别代表村落数 $n$ 和山贼集团部门数量 $p$ 。

第 $2$ 到第 $n$ 行，每行有两个整数 $x, y$ ，代表存在一条连接村落 $x$ 和村落 $y$ 的道路。

第 $(n + 1)$ 到第 $2n$ 行，每行 $p$ 个整数，第 $(i + n)$ 行的第 $j$ 个整数代表在第 $i$ 个村落建设第 $j$ 个部门的花费 $a_{i, j}$ 。

第 $(2n + 1)$ 行有一个整数，代表集团间相互影响利益的信息条数 $t$ 。

第 $(2n + 2)$ 行到第 $(2n + t + 1)$ 行，每行首先有一个整数 $v$ ，若 $v$ 为正，则表示会获得额外的收益， $v$ 为负则表示会有损失。然后有一个整数 $c$ ，代表涉及分部的数量。接下来有 $c$ 个整数，分别代表涉及的分部 $x_i$ 。本条信息的含义为若这 $c$ 个分部同时管辖某个小村落（可能同时存在其他分部管辖该村落），则会产生额外收益或损失，其数值大小为 $|v|$ 。

# 分析

首先，我们来简化一下题意，给我一棵树，对于树上的每一个节点，可能被多种颜色覆盖，如果给一个点染上了色，则从该节点到根节点的路径上的所有点都会被染上这个颜色，同时每个节点都设置了一个权值，当且仅当该点的颜色的集合为给定的集合，同时给不同点的染不同的颜色的代价不同，要求出最大的收益，每个分部只能建造一次。

我们肯定很快的就会有一个想要 $\texttt{dp}$ 的冲动，我们又一看 $p$ 的数据范围，发现很小，同时我们想要获得权值需要满足一个集合，所以我们就会自然而然的产生一个想法，我们可以状压表示每个点的颜色状态，那么我们直接树上 $\texttt{dp}$ ，枚举每个子节点的颜色的状态，然后合并。我们设 $dp[i][s]$ 为在 $i$ 号节点，其颜色状态为 $s$ ， $val[s]$ 表示当 $s$ 集合中的所有颜色染到一个点上的值，即当子树的颜色状态为 $s$ 时对于 $i$ 造成的影响。我们设新加入的子树的状态为 $w$ ，加入前的状态为 $s$ ，那么我们的转移方程为 $dp[i][s | w] = max(dp[i][s] + dp[j][w]) + val[s | w]$ 。

代码如下

	namespace Solve
	{
	using namespace read_write;

	const int N = 100 + 10;

	int n, t, m;
	int a[N], val[1 << 12];
	int h[N], dp[N][1 << 12], idx;

	struct Edge
	{
	int ne, v;
	} e[N << 1];

	void add(int u, int v)
	{
	e[++ idx].v = v, e[idx].ne = h[u], h[u] = idx;
	}

	void dp(int u, int fa)
	{
	for(int i = h[u] ; i ; i = e[i].ne)
	{
	int v = e[i].v;
	if(v == fa)
	continue;
	dp(v, u);
	for(int j = (1 << m) - 1 ; j ; -- j) // 枚举所有状态
	for(int k = j ; k ; k = (k - 1) & j) // 枚举子集
	dp[u][j] = max(dp[u][j], dp[u][j ^ k] + dp[v][k]);
	}

	for(int i = (1 << m) - 1 ; i ; -- i) // 每种状态加上路径的影响
	dp[u][i] += val[i];
	}

	void solve()
	{
	read(n), read(m);

	for(int i = 1 ; i < n ; ++ i)
	{
	int u, v;
	read(u), read(v);
	add(u, v), add(v, u);
	}

	for(int i = 1 ; i <= n ; ++ i)
	{
	for(int j = 1 ; j <= m ; ++ j)
	read(a[j]);
	for(int j = 1 ; j < (1 << m) ; ++ j) // 在一开始就直接讲建造造成的影响减去
	{
	int lb = j & -j;
	int id = log2(lb) + 1.00001; // 求最后一位 1 的位置
	dp[i][j] = dp[i][j ^ lb] - a[id];
	}
	}

	read(t);
	while(t -- )
	{
	int v, cnt, sum = 0;
	read(v), read(cnt);
	for(int j = 1 ; j <= cnt ; ++ j)
	{
	int flag;
	read(flag);
	sum \|= 1 << (flag - 1);
	}

	int mx = (1 << m) - 1;
	int tmp = sum ^ mx;
	val[sum] += v;

	for(int j = tmp ; j ; j = (j - 1) & tmp) // 预处理影响
	val[sum \| j] += v;
	}

	dp(1, 0);
	write(dp[1][(1 << m) - 1]);
	}
	}

	int main()
	{
	Solve :: solve();

	return 0;
	}

无关紧要的东西

这道题写于 2023.8.30，~~没错就是赛马娘国服开服的那一天~~，实际上没有做这道题没有任何特殊寓意，只是翻 dp 题的时候看到这个题目名的时候突然想起了一个人，然后才做这道题，反正不重要，无所谓了。（doge

题解动态规划

# SDOI2008 山贼集团

# 题目描述

# 输入格式

# 分析

平衡树全家桶

NOI2009 二叉查找树