[洛谷P4395][题解][BOI2003]Gem 气垫车

0.咕

又水了一篇题解qwq

1.解法

12染色和123染色都是错的，我们考虑直接暴力\(dp\)。
设\(f[i][j]\)为\(i\)填\(j\)时\(i\)子树的最小值。
方程很简单：\(f[now][j]=\sum_{k\ne j} \min(f[son][k])\)。
氮素！这个方程是\(O(n^3)\)的！
怎么办？
我们发现有很多数是没必要填的，也就是转移的\(O(n^2)\)是不需要跑满的。
题解区有最大数\(\log n\)的证明，自己做的时候随便选一个能过的数就行了。

2.代码

#define N 10010
int n,f[N][20],ans=INF;
struct Edge {
	int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void ade(int u,int v){
	e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
void DFS(int now,int ff){
	for(rg int i=1;i<20;i++)f[now][i]=i;
	for(rg int i=head[now];i;i=e[i].nxt){
		int v=e[i].to;
		if(v!=ff){
			DFS(v,now);
			for(rg int j=1;j<20;j++){
				int res=INF;
				for(rg int k=1;k<20;k++){
					if(j!=k)res=min(res,f[v][k]);
				}
				f[now][j]+=res;
			}
		}
	}
}
int main(){
	Read(n);
	for(rg int i=1;i<n;i++){
		int u,v;Read(u),Read(v),ade(u,v),ade(v,u);
	}
	DFS(1,0);
	for(rg int i=1;i<20;i++)ans=min(ans,f[1][i]);
	cout<<ans<<endl;
	return 0;
}

3.后记

按照\(\log n\)的大小把代码里的20改成14，一跃成为最优解……
有图为证（前两个都是改后代码区别只有\(O2\)）：