[hdu7042]二叉树

考虑最后这棵二叉树的结构，不难发现被移动的点在原树或新树中构成的都是若干棵完整的子树

（若$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 }

巴特西

[hdu7042]二叉树

最新文章

热门文章