command_block 的博客

command_block 的博客

[??记录]CF765E Tree Folding

posted on 2021-11-16 20:46:34 | under 记录 |

题意 : 给出一棵 $n$ 个点的无向无根树,可以进行如下操作:

  • 选择点 $t,u,v$ ,使得路径 $(u,t),(v,t)$ 除了节点 $t$ 没有多余的边,且满足 $dis(u,t)=dis(v,t)$。

    将 $(v,t)$ (不含 $t$)删去。(也可以理解为叠合)

判断能否将树转化为一条链,并最小化这条链的长度。

$n\leq 2\times 10^5$ ,时限$\texttt{2s}$。


对于一种方案,考虑其最后一次操作。

若选择的 $t$ 在链的一端,则将最后一次操作撤回,相当于将链倍长。

如此反复撤回,知道 $t$ 在链的中间。不难证明,此时链的两端必然为叶子。

我们考虑枚举每对叶子 $a,b$。考虑先将原树变为路径 $(a,b)$ ,再不断对折。

钦定 $(a,b)$ 之后,分别处理链上各个点的子树。

若子树内无法转化为一条链,无解。(转化为一条链的充要条件是所有叶子深度都相同)

可以发现,一定存在一条分界线,使得左边的子树向左倒,右边的子树向右倒。

我们取分界点(分界线旁边任取)为根,规定只能子树内合并,是等效的。确定根后的合并非常简单。

于是,算法改进为只需枚举根。

确定根后,能合成一条链的充要条件是:叶子的深度只有 $\leq 2$ 种。


进一步简化方案。考虑直径。

当根不在直径上时,能合成一条链的必要条件有:直径在某个子树内对折了,且直径到根的路径上没有其他分支。

对于这种情况,根选在直径中点是完全等价的。因此,我们只用考虑根在直径上的情况。

我们先单独尝试一次根为直径中点(可以证明,只可能有一个)的情况。

对于根不在直径中点的情况,直径两端就构成了两种不同的叶子深度。因此可以认为最后留下的一定是一条直径。

我们令 $(a,b)$ 为任意一条直径,尝试一次即可。

复杂度 $O(n)$。

#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define lbit(x) ((x)&-(x))
#define MaxN 200500
using namespace std;
vector<int> g[MaxN];
int tp,f[MaxN],dep[MaxN];
void dfs(int u,int fa)
{
  dep[u]=dep[f[u]=fa]+1;
  if (dep[u]>dep[tp])tp=u;
  for (int i=0;i<g[u].size();i++)
    if (g[u][i]!=fa)dfs(g[u][i],u);
}
int sl[MaxN],tot;
void dfs2(int u,int fa)
{
  if (g[u].size()==1)sl[++tot]=u;
  for (int i=0;i<g[u].size();i++)
    if (g[u][i]!=fa)dfs2(g[u][i],u);
}
bool vis[MaxN];
int n,st[MaxN],tn;
int main()
{
  scanf("%d",&n);
  for (int i=1,u,v;i<n;i++){
    scanf("%d%d",&u,&v);
    g[u].pb(v);g[v].pb(u);
  }dep[0]=-1;dfs(1,0);dfs(tp,0);
  for (int p=tp;p;p=f[p])vis[st[++tn]=p]=1;
  int ans=n;
  bool fl=0;int mode=0;
  for (int k=1;k<=tn;k++){
    int u=st[k];
    bool e=0;
    for (int i=0;i<g[u].size();i++)if (!vis[g[u][i]]){
      tot=0;
      dfs2(g[u][i],u);
      if (!tot)continue;
      for (int i=2;i<=tot;i++)
        if (dep[sl[1]]!=dep[sl[i]])fl=1;
      if ((dep[sl[1]]-(tn-k)!=k-1||mode==1)&&dep[sl[1]]-(tn-k)!=tn-k)fl=1;
      if (dep[sl[1]]-(tn-k)!=k-1)e=1;
    }if (e)mode=1;
  }
  if (!fl)ans=min(ans,(tn-1)/lbit(tn-1));
  if (tn&1){
    int a=0,b=0;fl=0;
    int rt=st[(tn+1)/2];dfs(rt,0);
    for (int i=0;i<g[rt].size();i++){
      tot=0;
      dfs2(g[rt][i],rt);
      if (!tot)continue;
      for (int i=2;i<=tot;i++)
        if (dep[sl[1]]!=dep[sl[i]])fl=1;
      int x=dep[sl[1]];
      if (!a)a=x;
      else if (a!=x){
        if (!b)b=x;
        else if (b!=x)fl=1;
      }
    }if (!fl)ans=ans=min(ans,(a+b)/lbit(a+b));
  }
  printf("%d",ans==n ? -1 : ans);
  return 0;
}