普陀学校网站建设新闻发布会稿件

题目大意

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

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

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

$1\le n\le 10^6$

时间限制$2000ms$，空间限制$256MB$。

题解

看这道题之前可以先看看AGC034E Complete Compress，本题为其加强版。

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

设$di{s}_u$表示$u$的子树中每个棋子到$u$的距离，那每一次操作会使$di{s}_r$减少$2$或者不变。我们发现， 如果不变的话，相当于浪费了一次，所以最优的肯定是选择减少$2$。

每次减少$2$，要不是在$r$的一个儿子的$dis$值减少$2$，要不是在$r$的两个儿子分别减少$1$。我们考虑什么时候无解，无解就是子树不能抵消完。设$m{n}_u$表示子树$u$中的棋子在内部操作若干次，直到不能再操作时的$di{s}_u$（也就是需要与其他子树操作的最小次数）。设$v$为$u$的儿子，我们比较$m{n}_v+si{z}_v$和$di{s}_u-di{s}_v-si{z}_v$的大小（$si{z}_v$表示子树$v$中的棋子个数）：

• 如果$m{n}_v+si{z}_v\le di{s}_u-di{s}_v-si{z}_v$，那就是能抵消完，最后剩的就是$m{n}_u=di{s}_u\%2$
• 如果$m{n}_v+si{z}_v>di{s}_u-di{s}_v-si{z}_v$，就不能抵消完，那我们拿其他部分来抵消$m{n}_v$，$m{n}_u=m{n}_v+si{z}_v-(di{s}_u-di{s}_v-si{z}_v)$

我们记录$u$的所有儿子$v$的$m{n}_v+di{s}_v+2si{z}_v$的最大值$m{x}_u$，然后用这个最大值来与$di{s}_u$作比较即可。

最后，看$m{n}_r$是否为$0$。如果为$0$，则可以抵消完，则用$di{s}_r/2$来更新答案（这里的$di{s}_r$是最开始的$di{s}_r$）；否则，以$r$为最终聚集的点是无解的。

时间复杂度为$O(n^2)$。下面考虑优化。

我们可以用换根$DP$。设$su{m}_u$表示所有棋子到$u$的距离，然后和上面类似地维护$fadi{s}_u$表示以$u$为根节点，除去$u$的子树部分之外的所有棋子到$u$的距离，$fam{n}_u$表示以$u$为根节点时除去$u$子树部分之外的部分内部操作若干次，直到不能再操作时的$di{s}_u$。其实和上面的定义是类似的，只不过上面是在$u$的子树中，这里是在$u$的子树之外。

因为在更新$u$的儿子$v$的$fam{n}_v$时有可能用到自己的$m{n}_v+di{s}_v+2si{z}_v$，所以我们在记录$m{n}_v+di{s}_v+2si{z}_v$的最大值时还要记录次大值，$m{x}_{u,0/1}$分别表示最大值和次大值。

用与上面类似的方法来维护，然后对每个点判断是否有解，有解就更新答案。

时间复杂度为$O(n)$。

可以参考代码帮助理解。

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],fadis[N+5],sum[N+5],famn[N+5],mx[N+5][2];
char s[N+5];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs1(int u,int fa){siz[u]=(s[u]=='1');for(int i=r[u];i;i=l[i]){int v=d[i];if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];dis[u]+=dis[v]+siz[v];long long tmp=dis[v]+siz[v]*2+mn[v];if(tmp>mx[u][0]){mx[u][1]=mx[u][0];mx[u][0]=tmp;}else if(tmp>mx[u][1]) mx[u][1]=tmp;}if(mx[u][0]<=dis[u]) mn[u]=dis[u]%2;else mn[u]=mx[u][0]-dis[u];
}
void dfs2(int u,int fa){for(int i=r[u];i;i=l[i]){int v=d[i];if(d[i]==fa) continue;long long now=dis[u]-dis[v]-siz[v];fadis[v]=now+siz[1]-siz[v]+fadis[u];sum[v]=dis[v]+fadis[v];long long famx=mx[u][0],fasum=sum[u]-dis[v]-siz[v];if(famx==dis[v]+siz[v]*2+mn[v]) famx=mx[u][1];famx=max(famx,famn[u]+fadis[u]);if(famx<=fasum) famn[v]=fasum%2+siz[1]-siz[v];else famn[v]=famx-fasum+siz[1]-siz[v];long long mxd=max(mx[v][0],fadis[v]+famn[v]);if(mxd<=sum[v]&&sum[v]%2==0) ans=min(ans,sum[v]/2);dfs2(v,u);}
}
int main()
{
//	freopen("charlotte.in","r",stdin);
//	freopen("charlotte.out","w",stdout);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);}dfs1(1,0);if(mn[1]==0) ans=dis[1]/2;sum[1]=dis[1];dfs2(1,0);if(ans==1e18) printf("-1\n");else printf("%lld\n",ans);return 0;
}