【学习笔记边分树】【uoj400】【CTSC2018】暴力写挂

àì夳堔傛蜴生んèń 2021-12-23 01:43 245阅读 0赞

## 题目 ##

### 描述 ###

有两棵树\$T\$和\$T'\$，节点个数都为\$n\$，根节点都为\$1\$号节点;

求两两点之间  
$$

\\begin\{align\}  
depth(x) + depth(y) - depth(LCA(x,y)) - depth'(LCA'(x,y))  
\\end\{align\}  
\\  
其中depth(x)为x和1号节点的树上距离  
\\

$$  
的最大值；

### 范围 ###

$1 \\le n \\le 366666 $ ；

## 题解 ##

*  原式 = \$\\frac\{(dep(x) + dep(y) + dis(x,y)) \}\{2\} -dep'(x,y)\$ ;
 *  枚举第二颗树的节点\$u\$，只需要查询\$u\$的各个子树之间的答案；
 *  考虑查询一个对很多点的左边的式子时，可以直接用边分治；
 *  询问两个子树之间的答案也可以用边分治，复杂度是\$O(n^2log \\ n)\$的；
 *  注意到边分树是一个二叉树的结构，直接采用线段树和并的写法合并；
 *  学习了一下边分治：
    
     *  每次选择一条边\$(u,v)\$，使得两边的子树最大\$size\$最小，不断分治；
     *  考虑直接分析复杂度：
        
         *  这部分理论是\$cjl\$老师在济南讲课的时候说的，网上说了这个的好少。。。。
         *  设整棵树最大的度数为\$D\$，\$u\$的子树大小为\$s\$，不妨令:\$u \\ge n - s\$;
         *  \$u\$的子树大小最大的儿子的子树大小是\$p\$；
         *  直接有：$p \\ge \\frac\{s-1\}\{D-1\} $ ;
         *  同时由于\$(u,v)\$是最优的决策，一定有：$n - p \\ge s $；
         *  解得：$s \\le \\frac\{n(D-1) + 1\}\{D\} $ ；
         *  意思是每次的联通块大小是以约\$\\frac\{D-1\}\{D\}\$的倍数缩小;
     *  当\$D\$是个常数时复杂度是\$log\$的，所以直接考虑将图变成一颗二叉树；
        
         *  ![1101338-20190404074505085-1817115867.png][]
         *  黑色的点和边代表原图中的边，绿色的点和边代表虚点和虚边；  
            \-新图的大小为原图的两倍；
         *  注意对边权和点权的修改因题而异；
 *  另外意外看到\$dsu \\ on \\ tree\$ ；
    
     *  适用于一些删除比较麻烦的树上数据结构，不支持修改；
     *  \$dfs\$并树剖，当一个节点做完了存储了子树的信息；
     *  假设我们有一个支持插入和完全清零的全局数据结构\$Ds\$，一次操作是\$O(Ds)的\$;
     *  每次先做轻儿子，做完后枚举子树节点暴力清空和轻儿子子树有关的\$Ds\$信息；
     *  所以当做完\$u\$的所有儿子回溯到\$u\$时，\$Ds\$中只存在\$u\$的重儿子的子树的影响；
     *  再做一遍所有轻儿子的子树，插入到\$Ds\$中去；
     *  当一个点被遍历的时候一定是出现了一条轻链；
     *  一个点向上的轻链个数为\$O(log \\ n)\$的，所以为\$O(n log \\ n \\ Ds)\$；
     *  套用到本题得到一个\$O(n log^2 \\ n)\$的做法；
    
        //这份代码过不了uoj的extra test ,luogu上会Ｔ一个点，暂时还没有修改；
        #include<bits/stdc++.h>
        #define mk make_pair
        #define fi first
        #define se second
        #define pb push_back
        #define inf 1e18
        #define ll long long 
        using namespace std;
        const int N=366666<<2,M=22;
        int n,o,hd[N],cnt,rt,mn,Rt[N],ls[N],rs[N],fa[N];
        int vis[N],size,sz[N],d[N],tot,lc[N*M],rc[N*M];
        ll dep[N],dis[M][N],val[N],mxl[N*M],mxr[N*M],wv[N*M],ans=-inf;
        struct Edge{int v,nt,w;}E[N];
        typedef pair<int,int>pii;
        vector<pii>g[N];
        char gc(){
          static char*p1,*p2,s[1000000];
          if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
          return(p1==p2)?EOF:*p1++;
        }
        int rd(){
          int x=0,f=1;char c=gc();
          while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
          while(c>='0'&&c<='9'){x=x*10+c-'0';c=gc();}
          return x*f;
        }
        void upd(ll&x,ll y){if(x<y)x=y;}
        void adde(int u,int v,int w){
          E[o]=(Edge){v,hd[u],w};hd[u]=o++;
          E[o]=(Edge){u,hd[v],w};hd[v]=o++;
        }
        void dfs1(int u,int F){
          for(int i=0,lst=0;i<(int)g[u].size();++i){
              int v=g[u][i].fi,w=g[u][i].se;
              if(v==F)continue;
              dep[v]=dep[u]+w;dfs1(v,u);
              if(!lst){adde(u,v,w);lst=u;continue;}
              adde(lst,++cnt,0);adde(cnt,v,w);lst=cnt;
          }
        }
        void get_rt(int u,int F){
          sz[u]=1;
          for(int i=hd[u];~i;i=E[i].nt){
              int v=E[i].v;
              if(vis[i]||v==F)continue;
              get_rt(v,u);sz[u]+=sz[v];
              int t=max(size-sz[v],sz[v]);
              if(mn>=t)rt=i,mn=t;
          }
        }
        void calc(int d,int u,int F,ll now){
          dis[d][u]=now;
          for(int i=hd[u];~i;i=E[i].nt){
              int v=E[i].v;
              if(vis[i]||v==F)continue;
              calc(d,v,u,now+E[i].w);
          }
        }
        int solve(int u,int F){
          if(size==1){fa[u]=F;return u;}
          int now=++cnt;
          rt=-1;mn=size;get_rt(u,0);
          val[now]=E[rt].w;
          vis[rt]=vis[rt^1]=1;
          d[now]=d[fa[now]=F]+1;
          int v1=E[rt].v,v2=E[rt^1].v;
          calc(d[now],v1,0,0);
          calc(d[now],v2,0,0);
          size-=sz[v1];rs[now]=solve(v2,now);
          size=sz[v1];ls[now]=solve(v1,now);
          return now;
        }
        int ins(int x){
          for(int u=fa[x],v=x,lst=0;u;v=u,u=fa[u]){
              wv[++tot]=val[u];mxl[tot]=mxr[tot]=-inf;
              if(ls[u]==v)mxl[tot]=dep[x]+dis[d[u]][x],lc[tot]=lst;
              else mxr[tot]=dep[x]+dis[d[u]][x],rc[tot]=lst;
              lst=tot;
          }
          return tot;
        }
        int merge(int x,int y,ll&tmp){
          if(!x||!y)return x+y;
          upd(tmp,wv[x]+max(mxl[x]+mxr[y],mxl[y]+mxr[x]));
          mxl[x]=max(mxl[x],mxl[y]);
          mxr[x]=max(mxr[x],mxr[y]);
          lc[x]=merge(lc[x],lc[y],tmp);
          rc[x]=merge(rc[x],rc[y],tmp);
          return x;
        }
        void dfs2(int u,int F,ll now){ 
          Rt[u]=ins(u);
          upd(ans,dep[u]-now);
          ll tmp=-inf;
          for(int i=hd[u];~i;i=E[i].nt){
              int v=E[i].v;
              if(v==F)continue;
              dfs2(v,u,now+E[i].w); 
              Rt[u]=merge(Rt[u],Rt[v],tmp);
          }
          upd(ans,(tmp>>1)-now);
        }
        int main(){
        //    freopen("1.in","r",stdin);
        //    freopen("1.out","w",stdout);
          cnt=n=rd();
          memset(hd,-1,sizeof(hd));
          for(int i=1,u,v,w;i<n;++i){
              u=rd(),v=rd(),w=rd();
              g[u].pb(mk(v,w));
              g[v].pb(mk(u,w));
          }
          dfs1(1,0);
          mxl[0]=mxr[0]=wv[0]=-inf;
          size=cnt;solve(1,0);
          o=0;memset(hd,-1,sizeof(hd));
          for(int i=1;i<n;++i){
              int u=rd(),v=rd(),w=rd();
              adde(u,v,w);
          }
          dfs2(1,0,0);
          cout<<ans<<endl;
          return 0;
        }

转载于:https://www.cnblogs.com/Paul-Guderian/p/10652758.html

[1101338-20190404074505085-1817115867.png]: /images/20211220/ce2f223141d84ef092b4e0e076a9049a.png