树上染色 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 }
eg

看上去的复杂度是$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)$。