[atAGC034E]Complete Compress

先考虑枚举最后的点，并以其为根

首先，操作祖先-后代关系是没有意义的，因为以后必然有一次操作会操作祖先使其返回原来的位置，那么必然不如操作后代和那一个点（少一次操作）

考虑某一次操作，总深度和恰好减2，因此若有解，操作次数为深度和的一半

考虑dp，令$f_{k}$表示以$k$为根的子树经过若干次操作后，最小的深度和

考虑加入一棵以$son$为根的子树，有三种情况：

1.$f_{son}$大于之前所有子树内部节点的深度和，那么之前的子树中节点不在内部操作，全部与这棵子树抵消，剩下的深度即为$f_{k}$

2.之前子树内部最小的答案也大于了这棵子树内部的深度和，那么用这棵子树的深度和去抵消之前的深度

3.可以证明，一定有方案使得其能够比较完美的匹配，换言之根据奇偶性判断剩下0或1

更具体的，记$g_{k}$表示以$k$为根的子树内部初始深度和（相对于$k$），$sz_{k}$表示以$k$为根的子树内不节点个数，转移如下（$g_{k}$是不断加入子树，即记录之前所有子树内部深度和）：
$$
f_{k}=\begin{cases}(f_{son}+sz_{son})-g_{k}(g_{k}<f_{son}+sz_{son})\\ f_{k}-(g_{son}+sz_{son})(f_{k}>g_{son}+sz_{son})\\ (f_{k}+g_{son}+sz_{son})\mod\ 2\end{cases}
$$
（关于$g_{k}$的转移是$g_{k}=g_{k}+g_{son}+sz_{son}$）

最后判定$f_{root}$即可，时间复杂度为$o(n^{2})$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2005

 4 #define ll long long

 5 struct ji{

 6     int nex,to;

 7 }edge[N<<1];

 8 int E,n,x,y,ans,head[N],sz[N],g[N],f[N];

 9 char s[N];

10 void add(int x,int y){

11     edge[E].nex=head[x];

12     edge[E].to=y;

13     head[x]=E++;

14 }

15 void dfs(int k,int fa){

16     sz[k]=g[k]=f[k]=0;

17     if (s[k]=='1')sz[k]=1;

18     for(int i=head[k];i!=-1;i=edge[i].nex)

19         if (edge[i].to!=fa){

20             dfs(edge[i].to,k);

21             sz[k]+=sz[edge[i].to];

22             if (g[k]<f[edge[i].to]+sz[edge[i].to])f[k]=f[edge[i].to]+sz[edge[i].to]-g[k];

23             else{

24                 if (g[edge[i].to]+sz[edge[i].to]<f[k])f[k]-=g[edge[i].to]+sz[edge[i].to];

25                 else f[k]=((f[k]+g[edge[i].to]+sz[edge[i].to])&1);

26             }

27             g[k]+=g[edge[i].to]+sz[edge[i].to];

28         }

29 }

30 int main(){

31     scanf("%d%s",&n,s+1);

32     memset(head,-1,sizeof(head));

33     for(int i=1;i<n;i++){

34         scanf("%d%d",&x,&y);

35         add(x,y);

36         add(y,x);

37     }

38     ans=n*n;

39     for(int i=1;i<=n;i++){

40         dfs(i,0);

41         if (!f[i])ans=min(ans,g[i]/2);

42     }

43     if (ans==n*n)ans=-1;

44     printf("%d",ans);

45 }

巴特西

[atAGC034E]Complete Compress

最新文章

热门文章