【描述】
給一棵n個(gè)結(jié)點(diǎn)的樹，給每個(gè)點(diǎn)安排一個(gè)正整數(shù)編號(hào)，使得相鄰點(diǎn)具有不同的編號(hào)，編號(hào)的總和盡量小。
【輸入】
第一行：n(n<=50,000)
以下n-1行，每行兩個(gè)數(shù)u,v(1<=u,v<=n)，表示u 和v有一條邊
【輸出】
僅一行，為最小編號(hào)和
【樣例輸入】
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
【樣例輸出】
11
【分析】
f[i][j]表示i這個(gè)點(diǎn)標(biāo)j這個(gè)數(shù)所能到達(dá)的最小總值。控制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: