思路
应该很容易想到使用树形 dp。
令 \(f_{u,i}\) 代表，只考虑 \(u\) 为根的子树，\(u\) 的编号为 \(i\) 的情况下，最小的编号总和。
那么我们可以用 \(u\) 的儿子 \(v\) 来更新 \(f_{u,i}\)。
转移方程 \(f_{u,i}=\sum_{v\in son_u}\min f_{v,k}[i\neq k]+i\)。
那么可能染色的种数有多少种呢？
我们可以观察一下样例，发现，如果使用最小的 \(1\) 和 \(2\) 作为编号的话，至少也是 \(12\)，而正确答案呢，则是把一个有 \(3\) 个儿子的节点的编号定为 \(3\)，让儿子的编号从 \(2\) 变成 \(1\)。
不妨假设某个节点，可以填入的最小编号是 \(1\)，那么如果他有 \(2\) 个儿子时，就应该填 \(2\)，让儿子更小，以获得更小的答案。
那么再继续假设，它的儿子里也有类似的情况，导致它的儿子必须填 \(2\) 才能让答案更小，所以这个节点必须填 \(3\)。
那么，假设这个节点最后要填 \(x\)，就必然存在要填 \(x-1\)，\(x-2\)，\(x-3\) 等等的节点，可以发现如果 \(x\) 比较大，整个树的总结点数就非常大，如下图 \(x=4\) 的情况：
P.S.蒟蒻不清楚是不是节点最少的情况，如有错误欢迎指出。
首先观察编号为 \(3\) 的节点，他不止需要一个编号必须为 \(2\) 的儿子，还需要另外的 \(3\) 个儿子，不然的话，可以让编号为 \(3\) 的节点变为编号 \(1\)，然后让儿子为 \(2\) 来获得更小答案，并且让它的父节点编号也可能变小。
所以编号为 \(4\) 的节点需要两个编号为 \(2\) 的节点和 \(5\) 个编号为 \(1\) 的节点。
可以发现总结点数增长很快，差不多是 \(2^n\) 的样子，所以编号最大不超过 \(\log n\)。
差不多是 \(5\) 的样子，但是做的时候没细想，直接开了 \(20\) 绝对不会错。
AC code
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,e[100005],ne[100005],h[50005],idx=1,a,b,col[50005],dp[50005][20],ans=inf;
inline void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u,int fa)
{
for(int i=h[u];i;i=ne[i])
if(e[i]!=fa)
{
dfs(e[i],u);
for(int j=1;j<20;++j)
{
int res=inf;
for(int k=1;k<20;++k) if(j!=k) res=min(res,dp[e[i]][k]);
dp[u][j]+=res;
}
}
for(int i=1;i<20;++i) dp[u][i]+=i;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;++i) scanf("%d%d",&a,&b),add(a,b),add(b,a);
dfs(1,0);
for(int i=1;i<20;++i) ans=min(ans,dp[1][i]);
printf("%d",ans);
return 0;
}