考虑最后这棵二叉树的结构，不难发现被移动的点在原树或新树中构成的都是若干棵完整的子树
（若$x$被移动，则$x$在原树或新树的子树中所有点都会被移动）
先在原树中考虑此问题，对于每一棵由被移动的点所构成的极大的子树，将子树大小累加到这棵子树根的父亲的权值$a_{i}$上（初始为0），将深度和累加到答案上（深度定义为到这棵子树根的距离+1）
类似地，对新树也执行此操作，得到权值$b_{i}$（注意新树中深度的定义应该去掉"+1"）
下面，问题即要不断选择$(x,y)\in E$（注意一条边有两种选法），使得$a_{x}$增加1且$a_{y}$减小1，并且最小化操作次数，最终将答案加上这个操作次数
考虑每一条边被使用的次数，不难发现最小操作次数即$\sum_{u=1}^{n}\abs{\sum_{v在u的子树中}(a_{v}-b_{v})}$
对于$a_{i}$和$b_{i}$的选择，即令$f_{i,j}$表示以$i$为根的子树中，强制$i$不被移动且$\sum_{v在i的子树中}(b_{v}-a_{v})=j$的最小答案（仅考虑子树内的贡献），下面来考虑转移——
儿子分为被移动和未被移动的，都可以用背包处理，且还需要求出第2类的数量（不超过2），然后再枚举$b_{i}$并将对应的代价加入其中（显然是完全二叉树）
由于$\sum_{v在i的子树中}(b_{v}-a_{v})$并不保证是$\le sz_{v}$的，因此背包的复杂度为$o(n^{2})$
总复杂度即$o(tn^{3})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 struct Edge{ 5 int nex,to; 6 }edge[N<<1]; 7 int E,t,n,x,y,sum[N],head[N],sz[N],tot[N],g[N][3],gg[N][3],f[N][N]; 8 void add(int x,int y){ 9 edge[E].nex=head[x]; 10 edge[E].to=y; 11 head[x]=E++; 12 } 13 void dfs(int k,int fa){ 14 sz[k]=1,tot[k]=0; 15 for(int i=head[k];i!=-1;i=edge[i].nex) 16 if (edge[i].to!=fa){ 17 dfs(edge[i].to,k); 18 sz[k]+=sz[edge[i].to]; 19 tot[k]+=tot[edge[i].to]; 20 } 21 tot[k]+=sz[k]; 22 memset(g,0x3f,sizeof(g)); 23 g[0][0]=0; 24 for(int i=head[k];i!=-1;i=edge[i].nex) 25 if (edge[i].to!=fa){ 26 memcpy(gg,g,sizeof(g)); 27 for(int j=n;j>=0;j--) 28 for(int p=0;p<3;p++)g[j][p]+=tot[edge[i].to]; 29 for(int l=0;l<=n;l++) 30 for(int j=l;j<=n;j++) 31 for(int p=1;p<3;p++)g[j][p]=min(g[j][p],gg[j-l][p-1]+f[edge[i].to][l]); 32 } 33 for(int i=0;i<=n;i++){ 34 f[k][i+1]=min(min(g[i][0],g[i][1]),g[i][2]); 35 for(int j=1;j<=i;j++){ 36 f[k][i+1]=min(f[k][i+1],g[i-j][0]+sum[j>>1]+sum[j+1>>1]); 37 f[k][i+1]=min(f[k][i+1],g[i-j][1]+sum[j]); 38 } 39 } 40 for(int i=0;i<=n;i++)f[k][i]+=abs(i-sz[k]); 41 } 42 int main(){ 43 for(int i=1;i<N;i++)sum[i]=sum[i>>1]+sum[i-1>>1]+i-1; 44 scanf("%d",&t); 45 while (t--){ 46 scanf("%d",&n); 47 E=0; 48 memset(head,-1,sizeof(head)); 49 for(int i=1;i<n;i++){ 50 scanf("%d%d",&x,&y); 51 add(x,y); 52 add(y,x); 53 } 54 dfs(1,0); 55 printf("%d\n",f[1][n]); 56 } 57 return 0; 58 }