[bzoj1369][Baltic2003]Gem_树形dp_结论题

Gem bzoj-1369 Baltic-2003

题目大意：给你一棵树，让你往节点上添自然数，使得任意相邻节点的数不同且使得权值最小。

注释：n为结点个数，$1\le n\le 10^3$。

想法：呵呵，学长一直在骂结论题，我一直觉得没啥.. ...

知道tm碰见这玩意儿，卧槽？！

树上相邻节点不同色，颜色个数最小值至多为logn。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <vector>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int n,cnt;

int last[10005],f[10005][25];

struct edge

{

	int to,next;

}e[20005];

void insert(int u,int v)

{

	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;

}

void dp(int x,int fa)

{

	for(int j=1;j<=20;j++)

		f[x][j]=j;

	for(int i=last[x];i;i=e[i].next)

		if(e[i].to!=fa)

			dp(e[i].to,x);

	for(int j=1;j<=20;j++)

	{

		for(int i=last[x];i;i=e[i].next)

			if(e[i].to!=fa)

			{

				int mn=inf;

				for(int k=1;k<=20;k++)

					if(j!=k)mn=min(mn,f[e[i].to][k]);

				f[x][j]+=mn;

			}

	}

}

int main()

{

	n=read();

	for(int i=1;i<n;i++)

	{

		int u=read(),v=read();

		insert(u,v);

	}

	dp(1,0);

	int ans=inf;

	for(int i=1;i<=20;i++)

		ans=min(ans,f[1][i]);

	printf("%d\n",ans);

	return 0;

}

小结：多做一些结论题吧... ...