本文共 790 字，大约阅读时间需要 2 分钟。

题目

思路

这两个问题，确实都是 $\mathtt{N}\mathtt{P}-\mathtt{H}\mathtt{a}\mathtt{r}\mathtt{d}$ 问题……那怎么做的出来呀？

但是 只需要解决其中一个，那就可以随便乱搞了。这是什么神仙题啊。

我们使用这样的方案：$\mathtt{d}\mathtt{f}\mathtt{s}$ 对点进行染色。一个点的颜色设置成其中一个邻接点的颜色 $+1$ ，且与邻接点的颜色均不同。比如可以设置为 $\text{mex}$ 。注意我们并没有要求 $color\le k$ ，我们只是单纯地将其染色而已。没有被确定颜色的邻接点就忽略。最先开始的点，颜色设置为 $1$ 。

染色结束之后，如果所有点的颜色都不大于 $k$ ，则问题一解决（根据染色的要求二）；如果有点的颜色大于 $k$ ，则问题二解决（根据染色的要求一，其邻接点中有一个的颜色恰好减少一，这个邻接点也存在一个邻接点的颜色恰好再减少一，直到颜色变为 $1$ ，则此路径长度为 $k$）。

代码

此处仅提供伪代码作为参考。

int color[MaxN];void dfs(int x){   	int mx = 0;	for(auto y : g[x]) // 使用邻接表,vector版本		mx = max(mx,color[y]);	color[x] = mx+1;	for(auto y : g[x])		if(color[y] == 0)			dfs(y);}void solve(){   	dfs(1);	bool colored = true;	for(int i=1; i<=n; ++i)		if(color[i] > k){   			输出路径;			colored = false;			break;		}	if(colored) 输出染色方案;}

转载地址：http://lqvq.baihongyu.com/