BZOJ1369:[Baltic2003]Gem(树形DP)

Description

给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。

Input

先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连

Output

最小的总权值

Sample Input

10
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3

Sample Output

Solution

结论题。权值标号不会大于$log2(n)$。

Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #define N (10009)
 5 using namespace std;
 6 
 7 struct Edge{int to,next;}edge[N<<1];
 8 int n,u,v,f[N][30],ans=1e9,LOG2,head[N],num_edge;
 9 
10 void add(int u,int v)
11 {
12     edge[++num_edge].to=v;
13     edge[num_edge].next=head[u];
14     head[u]=num_edge;
15 }
16 
17 void Dfs(int x,int fa)
18 {
19     for (int v1=1; v1<=LOG2; ++v1) f[x][v1]=v1;
20     for (int i=head[x]; i; i=edge[i].next)
21         if (edge[i].to!=fa)
22             Dfs(edge[i].to,x);
23     for (int v1=1; v1<=LOG2; ++v1)
24     {
25         for (int i=head[x]; i; i=edge[i].next)
26             if (edge[i].to!=fa)
27             {
28                 int minn=1e9;
29                 for (int v2=1; v2<=LOG2; ++v2)
30                     if (v2!=v1) minn=min(minn,f[edge[i].to][v2]);
31                 f[x][v1]+=minn;
32             }
33     }
34 }
35 
36 int main()
37 {
38     scanf("%d",&n);
39     LOG2=ceil(log10(1.0*n)/log10(2.0));
40     for (int i=1; i<=n-1; ++i)
41         scanf("%d%d",&u,&v), add(u,v), add(v,u);
42     Dfs(1,0);
43     for (int i=1; i<=LOG2; ++i) ans=min(ans,f[1][i]);
44     printf("%d
",ans);
45 }