结论题。。。一棵树里用到的颜色数不超过logn。。
f[i][j]表示以i为根的子树里，i的颜色是j的方案数。
g[i][j]表示max{f[i][k]}，（k!=j
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=10233,inf=1e9+233; 7 struct zs{int too,pre;}e[maxn<<1];int tot,last[maxn]; 8 int f[maxn][23],g[maxn][23]; 9 int i,j,k,n,m; 10 11 int ra;char rx; 12 inline int read(){ 13 rx=getchar(),ra=0; 14 while(rx<'0'||rx>'9')rx=getchar(); 15 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 16 } 17 18 void dfs(int x,int fa){//printf("%d-->%d ",fa,x); 19 int i,j,mn=0,nd=0; 20 for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa){ 21 dfs(e[i].too,x); 22 for(j=1;j<23;j++)f[x][j]+=g[e[i].too][j]; 23 } 24 f[x][0]=inf; 25 for(i=1;i<23;i++){ 26 f[x][i]+=i; 27 if(f[x][i]<f[x][mn])nd=mn,mn=i; 28 else if(f[x][i]<f[x][nd])nd=i; 29 } 30 for(i=1;i<23;i++)if(i!=mn)g[x][i]=f[x][mn];else g[x][i]=f[x][nd]; 31 } 32 inline void insert(int a,int b){ 33 e[++tot].too=b,e[tot].pre=last[a],last[a]=tot, 34 e[++tot].too=a,e[tot].pre=last[b],last[b]=tot; 35 } 36 37 int main(){ 38 n=read(); 39 for(i=1;i<n;i++)insert(read(),read()); 40 dfs(1,0); 41 int ans=min(g[1][1],f[1][1]); 42 printf("%d ",ans); 43 return 0; 44 } 45