AGC034E Complete Compress

Complete Compress"/>

AGC034E Complete Compress

AGC034E Complete Compress

洛谷[AGC034E] Complete Compress

题目大意

给你一棵有 n n n个节点的树，并用 01 01 01串告诉你哪些节点上有棋子（恰好一棵）。

你可以进行若干次操作，每次操作可以将两颗距离至少为 2 2 2的棋子向彼此移动一步。

问能否通过若干次操作使得所有的棋子都在一个点上。如果能，输出最小操作次数；否则，输出 − 1 -1 −1。

2 ≤ n ≤ 2000 2\leq n\leq 2000 2≤n≤2000

时间限制 3000 m s 3000ms 3000ms，空间限制 1024 M B 1024MB 1024MB。

题解

我们可以枚举最后所有棋子聚集在哪个点，设这个点为 r r r，我们设 r r r为根。

设 d i s u dis_u disu​表示 u u u的子树中每个棋子到 u u u的距离，那每一次操作会使 d i s r dis_r disr​减少 2 2 2或者不变。我们发现， 如果不变的话，相当于浪费了一次，所以最优的肯定是选择减少 2 2 2。

每次减少 2 2 2，要不是在 r r r的一个儿子的 d i s dis dis值减少 2 2 2，要不是在 r r r的两个儿子分别减少 1 1 1。我们考虑什么时候无解，无解就是子树不能抵消完。设 m n u mn_u mnu​表示子树 u u u中的棋子在内部操作若干次，直到不能再操作时的 d i s u dis_u disu​（也就是需要与其他子树操作的最小次数）。设 v v v为 u u u的儿子，我们比较 m n v + s i z v mn_v+siz_v mnv​+sizv​和 d i s u − d i s v − s i z v dis_u-dis_v-siz_v disu​−disv​−sizv​的大小（ s i z v siz_v sizv​表示子树 v v v中的棋子个数）：

• 如果 m n v + s i z v ≤ d i s u − d i s v − s i z v mn_v+siz_v\leq dis_u-dis_v-siz_v mnv​+sizv​≤disu​−disv​−sizv​，那就是能抵消完，最后剩的就是 m n u = d i s u % 2 mn_u=dis_u\%2 mnu​=disu​%2
• 如果 m n v + s i z v > d i s u − d i s v − s i z v mn_v+siz_v>dis_u-dis_v-siz_v mnv​+sizv​>disu​−disv​−sizv​，就不能抵消完，那我们拿其他部分来抵消 m n v mn_v mnv​， m n u = m n v + s i z v − ( d i s u − d i s v − s i z v ) mn_u=mn_v+siz_v-(dis_u-dis_v-siz_v) mnu​=mnv​+sizv​−(disu​−disv​−sizv​)

我们记录 u u u的所有儿子 v v v的 m n v + d i s v + 2 s i z v mn_v+dis_v+2siz_v mnv​+disv​+2sizv​的最大值 m x u mx_u mxu​，然后用这个最大值来与 d i s u dis_u disu​作比较即可。

最后，看 m n r mn_r mnr​是否为 0 0 0。如果为 0 0 0，则可以抵消完，则用 d i s r / 2 dis_r/2 disr​/2来更新答案（这里的 d i s r dis_r disr​是最开始的 d i s r dis_r disr​）；否则，以 r r r为最终聚集的点是无解的。

时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

可以参考代码帮助理解。

题外话：这道题还有加强版，题意相同但数据范围更大，加强版的题目和题解请看这篇博客。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,tot=0,d[2*N+5],l[2*N+5],r[N+5],dep[N+5],siz[N+5];
long long ans=1e18,dis[N+5],mn[N+5],mx[N+5];
char s[N+5];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u,int fa){siz[u]=(s[u]=='1');dis[u]=0;mn[u]=0;mx[u]=0;for(int i=r[u];i;i=l[i]){int v=d[i];if(v==fa) continue;dfs(v,u);siz[u]+=siz[v];dis[u]+=dis[v]+siz[v];long long tmp=dis[v]+siz[v]*2+mn[v];mx[u]=max(mx[u],tmp);}if(mx[u]<=dis[u]) mn[u]=dis[u]%2;else mn[u]=mx[u]-dis[u];
}
int main()
{scanf("%d",&n);scanf("%s",s+1);for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i=1;i<=n;i++){dfs(i,0);if(mn[i]==0) ans=min(ans,dis[i]/2);}if(ans==1e18) printf("-1\n");else printf("%lld\n",ans);return 0;
}