[2017SEERC]Divide and Conquer

https://www.zybuluo.com/ysner/note/1308834

题面

一个有\(n\)个点的图，上面有有两棵不同的生成树。问至少切断几条边，可以使原图不联通。并输出方案数。

\(n\leq10^6\)

解析

或许是道树上差分模板题?

首先，由于只有\(2n-2\)条边，故所有点的最小度数只能为\(2\)或\(3\)（若度数为\(4\)，需要\(2n\)条边）。

所以答案也只能是\(2\)或\(3\)。

那么，肯定在某一棵生成树上只割了一条边。

一开始想法是枚举这条边是哪个，再查一查切断这条边后，该边两个端点被几条线段连接。

然而复杂度不对，差分\(O(n^2)\)，树链剖分+线段树\(O(nlog^2n)\)。

实际上把一棵树上的所有边都用来覆盖另一棵树（即覆盖两端点的树上路径），再统计一下哪条边被覆盖次数最少，\(+1\)（这棵树上只切一条边）就是答案。（代码中\(/2\)是因为边是双向的，都加了两次）

这个可以用差分来完成。

如果答案是\(3\)，则可能在另一棵树上只割一条边。反向覆盖+差分来统计方案数即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#define ll long long

#define re register

#define il inline

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=2e6+100;

int n,m,h[2][N],cnt[2],f[N],s[N],lca[N],vis[N],mn=1e9,ans;

struct Edge{int to,nxt;}e[2][N<<1];

il void add(re int u,re int v){e[m][++cnt[m]]=(Edge){v,h[m][u]};h[m][u]=cnt[m];}

il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il void dfs(re int u)

{

  vis[u]=1;

  for(re int i=h[m][u];i+1;i=e[m][i].nxt)

    {

      re int v=e[m][i].to;

      if(vis[v]) continue;

      dfs(v);

      f[v]=u;

    }

  for(re int i=h[m^1][u];i+1;i=e[m^1][i].nxt)

    {

      re int v=e[m^1][i].to;

      if(vis[v]==2) lca[i>>1]=find(v);

    }

  vis[u]=2;

}

il void calc(re int u,re int fa)

{

  for(re int i=h[m][u];i+1;i=e[m][i].nxt)

    {

      re int v=e[m][i].to;

      if(v==fa) continue;

      calc(v,u);

      s[u]+=s[v];

    }

  if(!fa) return;

  if((s[u]>>1)+1<mn) mn=(s[u]>>1)+1,ans=1;

  else if((s[u]>>1)+1==mn) ++ans;

}

il void solve()

{

  memset(s,0,sizeof(s));memset(vis,0,sizeof(vis));

  fp(i,1,n) f[i]=i;

  dfs(1);

  fp(u,1,n)

  for(re int i=h[m^1][u];i+1;i=e[m^1][i].nxt)

    {

      re int v=e[m^1][i].to;

      ++s[u];++s[v];s[lca[i>>1]]-=2;

    }

  calc(1,0);

}

int main()

{

  freopen("xianjian.in","r",stdin);

  freopen("xianjian.out","w",stdout);

  memset(h,-1,sizeof(h));cnt[0]=cnt[1]=1;

  n=gi();

  fp(i,1,2*n-2)

    {

      if(i==n) m=1;

      re int u=gi(),v=gi();

      add(u,v);add(v,u);

    }

  m=0;solve();

  if(mn==3) m=1,solve();

  printf("%d %d\n",mn,ans);

  fclose(stdin);

  fclose(stdout);

  return 0;

}

巴特西

[2017SEERC]Divide and Conquer

https://www.zybuluo.com/ysner/note/1308834

题面

解析

最新文章

热门文章