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

2019/04/04 07:42
阅读数 116

题目

描述

​ 有两棵树$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$的,所以直接考虑将图变成一颗二叉树;
      • 黑色的点和边代表原图中的边,绿色的点和边代表虚点和虚边; -新图的大小为原图的两倍;

      • 注意对边权和点权的修改因题而异;

  • 另外意外看到$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上会T一个点,暂时还没有修改; #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[NM],rc[NM]; ll dep[N],dis[M][N],val[N],mxl[NM],mxr[NM],wv[NM],ans=-inf; struct Edge{int v,nt,w;}E[N]; typedef pair<int,int>pii; vector<pii>g[N]; char gc(){ static charp1,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=x10+c-'0';c=gc();} return xf; } 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; }

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部