[2017SEERC]Divide and Conquer

差分 树形DP

题面

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

• $n\leq10^6$

解析

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

首先，由于只有$2n-2$条边，故所有点的最小度数只能为$2$或$3$（若度数为$4$，需要$2n$条边）。
所以答案也只能是$2$或$3$。

那么，肯定在某一棵生成树上只割了一条边。
一开始想法是枚举这条边是哪个，再查一查切断这条边后，该边两个端点被几条线段连接。
然而复杂度不对，差分$O(n^2)$，树链剖分+线段树$O(nlog^2n)$。

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

如果答案是$3$，则可能在另一棵树上只割一条边。反向覆盖+差分来统计方案数即可。
复杂度$O(n)$。(使用$Tarjan$求$LCA$)

#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;
}