以下均为内网
树上染色 https://www.lydsy.com/JudgeOnline/problem.php?id=4033
可怜与超市 http://hzoj.com/contest/62/problem/5
可以简单的列出状态转移方程。
它的转移过程类似：
1 void dfs(int x)
2 {
3 for(unsigned i=0;i<p[x].size();++i) dfs(p[x][i]);
4 int cur=0;
5 memset(tmp[cur],0x3f,sizeof(tmp[cur]));
6 tmp[cur][0][0]=tmp[cur][1][0]=0;
7 for(unsigned i=0;i<p[x].size();++i)
8 {
9 int now=sz[p[x][i]]; cur^=1;
10 memset(tmp[cur],0x3f,sizeof(tmp[cur]));
11 for(int j=0;j<=sz[x];++j)
12 for(int k=0;k<=now;++k)
13 {
14 tmp[cur][1][k+j]=min(tmp[cur][1][k+j],tmp[cur^1][1][j]+dp[1][p[x][i]][k]);
15 tmp[cur][1][k+j]=min(tmp[cur][1][k+j],tmp[cur^1][1][j]+dp[0][p[x][i]][k]);
16 tmp[cur][0][k+j]=min(tmp[cur][0][k+j],tmp[cur^1][0][j]+dp[0][p[x][i]][k]);
17 }
18 sz[x]+=now;
19 }
20 ++sz[x];
21 dp[0][x][0]=0; dp[1][x][0]=0;
22 for(int i=1;i<=sz[x];++i) dp[1][x][i]=tmp[cur][1][i-1]+wc[x];//db(dp[1][x][i]);
23 for(int i=1;i<=sz[x];++i) dp[0][x][i]=min(tmp[cur][0][i],tmp[cur][0][i-1]+c[x]);
24 }
看上去的复杂度是$O（n^3）$，
然而仔细分析，复杂度只有$O（n^2）$，可以通过n为5000左右的数据。
引入一个概念，（a，b）为树上的点对，则该点对在图中有$n^2$个
观察状态的转移，
在x节点范围内，设x有k个节点，
复杂度为：
$sum limits_{i=1}^{k}sum limits_{j=i}^{k}size_i*size_j$
我们发现这样求出来，恰好是lca为x的点对个数。
每个点对一定存在且仅存在一个lca，每个点对只会被统计不超过一次，
所以总的复杂度为$O(n^2)$。