【题解】[CQOI2005] 珠宝

题目信息
分析
注意事项
Code

题目信息

题目来源：CCF 重庆省选 2005；

在线评测地址：Luogu#5765；

运行限制：时间 (1.00 extrm{s})，空间 (128 extrm{MiB})。

（笔者没有在网上找到原题面，于是以下采用的是洛谷的精简题面）

题目描述

有一棵 (n) 个结点的树，给每个点安排一个正整数编号，使得相邻点具有不同的编号，编号的总和尽量小。

输入格式

第一行一个整数 (n)。

以下 (n-1) 行，每行两个数 (u,v)，表示 (u) 和 (v) 间有一条边。

输出格式

仅一行，为最小编号和。

数据规模与约定

对于 (20\%) 的数据，(nle 10)；
对于 (40\%) 的数据，(nle 10^3)；
对于 (100\%) 的数据，(1le nle 5 imes 10^4)。

保证 (1le u,vle n)。

分析

比较显然的树形 DP。（当时学树形 DP 的第一道例题就是这一个）

树上的问题通常要强行定根，然后进行 BFS 确定 DP 顺序，接下来进行 DP。这道题转移时要注意考虑这个节点的权值及其孩子的权值的可能性。

定义 (f_{i,j}) 为第 (i) 个点的权值为 (j) 时的最小值，则可以得到 (f_{i,j}=v_{i,j} + sumlimits_{i ightarrow p} min_{v=0}^{v eq j} f_{p,v})。

接下来的问题是 (j) 的上界，这将会直接影响到复杂度。经试验开到 (4) 即可。

注意事项

注意 BFS 完后要倒序DP。

Code

#include <cstdio>
#include <cstring>
using namespace std;

constexpr int max_n = 50000, max_v = 4;
struct node // 队列节点
{
	int id, fa;

	node(int _i = 0, int _f = -1) : id(_i), fa(_f) { }
};

int dp[max_n][max_v], hd[max_n], des[max_n<<1], nxt[max_n<<1], e_cnt = 0;
node que[max_n];

void add_edge(int s, int t)
{
	des[e_cnt] = t;
	nxt[e_cnt] = hd[s];
	hd[s] = e_cnt++;
}

int main()
{
	memset(hd, -1, sizeof(hd));

	int n, ta, tb, ql = 0, qr = 0;
	node cur;

	scanf("%d", &n);
	for (int i = 1; i < n; i++) // 输入，建图
	{
		scanf("%d%d", &ta, &tb);

		add_edge(ta - 1, tb - 1);
		add_edge(tb - 1, ta - 1);
	}

	que[qr++] = node();

	while (ql < qr) // BFS
	{
		cur = que[ql++];

		for (int p = hd[cur.id]; p != -1; p = nxt[p])
			if (des[p] != cur.fa)
				que[qr++] = node(des[p], cur.id); // 防止死循环，加上判断
	}

	for (int i = n - 1; i >= 0; i--)
		for (int j = 0; j < max_v; j++) // 第一重遍历
		{
			dp[que[i].id][j] = j;

			for (int p = hd[que[i].id]; p != -1; p = nxt[p])
			{
				ta = max_v * max_n;

				for (int k = 0; k < max_v; k++) // 第二重遍历
					if (j != k)
					{
						if (dp[des[p]][k] < ta) // 更小就更新
							ta = dp[des[p]][k];
					}
				
				dp[que[i].id][j] += ta;
			}
		}
	
	ta = max_v * max_n;
	for (int i = 0; i < max_v; i++) // 统计答案
		if (dp[0][i] < ta)
			ta = dp[0][i];
	
	printf("%d
", ta); // 输出

	return 0; // 然后就 AC 了、
}