边分治建图模板

边分治最怕菊花图
所以要对原图进行改造

https://blog.csdn.net/make_it_for_good/article/details/52194466

需要用vector存储邻接表
方法妙不可言
0边是虚边，1边是实边

for(int x=1;x<=n;x++) {   
       int t=a[x].size();
       if(t==0)continue;
       if(t==1) {
           add(x,a[x][0],1);add(a[x][0],x,1);
           continue;
       }
       for(int i=2;i<t<<1;i<<=1)
           for(int j=0;j<t;j+=i) {
               add(++n,a[x][j],i==2 ? 1:0);
               add(a[x][j],n,i==2 ? 1:0);
               a[x][j]=n;v[n]=v[x];
               if(j+(i>>1)<t) {   
                   add(n,a[x][j+(i>>1)],i==2 ? 1:0);
                   add(a[x][j+(i>>1)],n,i==2 ? 1:0);
               }
           }
       add(n,x,0);add(x,n,0);
   }