UOJ#400. 【CTSC2018】暴力寫掛 邊分治 線段樹合并
原文鏈接 www.rzrgm.cn/zhouzhendong/p/UOJ400.html
前言
老年選手沒有碼力。
題解
先對第一棵樹進行邊分治，然后，設點 x 到分治中心的距離為 $D[x]$，點 x 在原樹上的深度為 $d[x]$，那么
$$d[x]+d[y] - d[LCA(x,y)] - d'[LCA(x,y)] = \frac 12(D[x] + d[x]) + \frac 12 (D[y] + d[y]) - d'[LCA(x,y)]$$
于是我們考慮將分治區域內的節點在第二棵樹上建虛樹，并 DFS，每次維護一下子樹中的 max(D[x] + d[x]) ，合并到父親時順便算一下答案。
類似于WC2018通道，這樣做的時間復雜度是可以強行優化成 $O(n\log n)$ 的。
但是本題有更巧妙的做法。
考慮邊分樹這個數據結構。它具有幾個性質：
1. 深度為 $O(\log n)$，準確地說是略大于 $\log _2 n $ 的，約等于 $\log_{1.5} n$。（嗯對，xza深度只開了20，被我hack了\kel）
2. 葉子節點個數為 $n$ 。
如果任取一種 DFS 序，并將其葉子按順序排列，那么，兩組節點的邊分樹合并的過程就可以看做以葉子 DFS 序為定義域的線段樹合并。時間復雜度證明和線段樹合并相同。寫法也幾乎相同。
于是，我們得到下面的優秀算法：
首先對第一棵樹進行邊分治，建出邊分樹。
然后對第二棵樹進行 DFS，用“邊分樹合并”來支持子樹合并操作。在邊分樹合并的同時計算答案。 我們要維護的值僅僅是邊分時兩半集合中節點的權值 max 。
時間復雜度 $O(n\log n)$ 。
代碼
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=a;i<=b;i++)
using namespace std;
typedef long long LL;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=366677*2,S=N*13;
const LL LLINF=1e18;
struct Graph{
static const int M=N*2;
int cnt,y[M],fst[N],nxt[M],z[M];
void clear(){
cnt=1,clr(fst);
}
void add(int a,int b,int c){
y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt,z[cnt]=c;
}
void Add(int a,int b,int c){
add(a,b,c),add(b,a,c);
}
}t1,t2,T1;
#define Forg(g) for (int E=g.fst[x],y=g.y[E];E;E=g.nxt[E],y=g.y[E]) if (y!=pre)
int n,vcnt,ec;
int td[N],vis[N],pos[N];
LL d[N],val[27][N];
void GetT1(int x,int pre,LL D){
int t=x,v;
d[x]=D;
Forg(t1)
d[v=++vcnt]=D,T1.Add(t,v,0),T1.Add(v,y,t1.z[E]),t=v,GetT1(y,x,D+t1.z[E]);
}
namespace DT{
int size[N],Mx[N],nowsize,kx,ky,kz;
void GetRT(int x,int pre,int flen){
size[x]=1;
Forg(T1)
if (!vis[y])
GetRT(y,x,T1.z[E]),size[x]+=size[y];
Mx[x]=max(size[x],nowsize-size[x]);
if (!kx||Mx[x]<Mx[kx])
kx=x,ky=pre,kz=flen;
}
void dfs(int x,int pre,LL D,int w){
pos[x]|=w<<td[x],val[td[x]++][x]=D+d[x];
Forg(T1)
if (!vis[y])
dfs(y,x,D+T1.z[E],w);
}
void Divide(int x,int Size){
if (Size>1){
kx=0,nowsize=Size,GetRT(x,0,0),x=kx;
int y=ky,z=kz,tmp=size[x];
dfs(x,y,0,0),dfs(y,x,z,1);
vis[y]=1,Divide(x,tmp),vis[y]=0;
vis[x]=1,Divide(y,Size-tmp);
}
}
}
int rt[N],ls[S],rs[S];
LL Lmx[S],Rmx[S],ans=-LLINF;
int st[S],top,cnt=0;
int NewNode(){
return top?st[top--]:++cnt;
}
void RecNode(int x){
ls[x]=rs[x]=Lmx[x]=Rmx[x]=0,st[++top]=x;
}
void Ins(int &rt,int x,int D){
if (D<td[x]){
rt=NewNode(),Lmx[rt]=Rmx[rt]=-LLINF;
if (pos[x]>>D&1)
Ins(rs[rt],x,D+1),Rmx[rt]=max(Rmx[rt],val[D][x]);
else
Ins(ls[rt],x,D+1),Lmx[rt]=max(Lmx[rt],val[D][x]);
}
}
int Merge(int x,int y,LL add){
if (!x||!y)
return x|y;
ans=max(ans,max(Lmx[x]+Rmx[y],Rmx[x]+Lmx[y])/2+add);
Lmx[x]=max(Lmx[x],Lmx[y]),Rmx[x]=max(Rmx[x],Rmx[y]);
ls[x]=Merge(ls[x],ls[y],add),rs[x]=Merge(rs[x],rs[y],add);
return RecNode(y),x;
}
void Solve(int x,int pre,LL D){
ans=max(ans,d[x]-D),Ins(rt[x],x,0);
Forg(t2)
Solve(y,x,D+t2.z[E]),rt[x]=Merge(rt[x],rt[y],-D);
}
int main(){
n=read(),t1.clear(),t2.clear(),T1.clear();
For(i,1,n-1){
int x=read(),y=read(),z=read();
t1.Add(x,y,z);
}
For(i,1,n-1){
int x=read(),y=read(),z=read();
t2.Add(x,y,z);
}
vcnt=ec=n,GetT1(1,0,0),DT::Divide(1,vcnt),Solve(1,0,0);
cout<<ans<<endl;
return 0;
}
浙公網安備 33010602011771號