【描述】
给一棵n个结点的树，给每个点安排一个正整数编号，使得相邻点具有不同的编号，编号的总和尽量小。
【输入】
第一行：n(n<=50,000)
以下n-1行，每行两个数u,v(1<=u,v<=n)，表示u 和v有一条边
【输出】
仅一行，为最小编号和
【样例输入】
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
【样例输出】
11
【分析】
f[i][j]表示i这个点标j这个数所能到达的最小总值。控制j的范围到30肯定过。
1: #include <stdio.h>
2: #include <iostream>
3: #define MAXINT 10000000
4: #define maxn 50010
5: using namespace std;
6:
7: int f[maxn][31];
8: int bl[maxn][maxn/100];
9: int son[maxn][maxn/100],root[maxn];
10: int n;
11: int x,y;
12: int ans=MAXINT;
13:
14: void maket(int x)
15: {
16: for (int i=1;i<=bl[x][0];++i)
17: {
18: int k=bl[x][i];
19: if (k==root[x]) continue;
20: son[x][++son[x][0]]=k;
21: root[k]=x;
22: maket(k);
23: }
24: }
25:
26: void dp(int x)
27: {
28: if (f[x][1]) return;
29: for (int i=1;i<=30;++i)
30: {
31: for (int j=1;j<=son[x][0];++j)
32: {
33: int tt=son[x][j];
34: dp(tt);
35: int minn=MAXINT;
36: for (int jj=1;jj<=30;++jj)
37: if (jj!=i)
38: if (f[tt][jj]<minn)
39: minn=f[tt][jj];
40: f[x][i]+=minn;
41: }
42: f[x][i]+=i;
43: }
44: }
45:
46: int main()
47: {
48: freopen("gems.in","r",stdin);
49: freopen("gems.out","w",stdout);
50:
51: scanf("%d",&n);
52: for (int i=1;i<n;++i)
53: {
54: scanf("%d%d",&x,&y);
55: bl[x][++bl[x][0]]=y;
56: bl[y][++bl[y][0]]=x;
57: }
58: maket(1);
59: dp(1);
60: for (int i=1;i<=30;++i)
61: if (f[1][i]<ans)
62: ans=f[1][i];
63: printf("%d\n",ans);
64: return 0;
65: }
66: