P4220 [WC2018]通道 题解
题面
跟暴力写挂有点像，但是这次是三棵树的距离之和最大。考虑在第一棵树上点分治，合并两个儿子子树，求其中的最大值。这个过程可以合并果子，花费 \(1\log\)。在合并的时候拿出这些点来在第二棵树上建虚树，在虚树上 dp，每个位置维护子树内分别在要合并的两个子树（设为 \(0,1\)）的直径（包括第三棵树）。这样在每个位置统计以这个位置作为第二棵树上 \(lca\) 的路径最大值。复杂度 \(O(n\log^2 n)\)。
点击查看代码
inline void clearvector(std::vector &a){std::vector b;std::swap(a,b);}
const int N=1e5+13;
struct Edge{int v;ll w;int nxt;};
int n;ll ans;
namespace tree2{ll dis[N];bool vis[N];inline void build(std::vector a);}
namespace tree3{
inline ll calc(int u,int v);
struct Node{
int x,y;ll d;
inline bool operator <(const Node &a)const{return d>a.d;}
inline Node operator +(const Node &a)const{
static Node b[6];b[0]=(Node){x,y,d},b[1]=(Node){a.x,a.y,a.d};
b[2]=(Node){x,a.x,calc(x,a.x)},b[3]=(Node){x,a.y,calc(x,a.y)};
b[4]=(Node){y,a.x,calc(y,a.x)},b[5]=(Node){y,a.y,calc(y,a.y)};
int o=0;for(int i=1;i<6;++i)if(b[i] g[N];
ll dis[N];
void findrt(int u,int f){
siz[u]=1,maxx[u]=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f||vis[v]) continue;
findrt(v,u);
siz[u]+=siz[v];
maxx[u]=max(maxx[u],siz[v]);
}
maxx[u]=max(maxx[u],psum-siz[u]);
if(maxx[u] t;t.insert(mp(g[u].size(),u));
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(vis[v]) continue;
clearvector(g[v]);
dfs(v,u,e[i].w,v);
t.insert(mp(g[v].size(),v));
}
while(t.size()>1){
std::set::iterator it=t.begin();int x=it->se;t.erase(it);
it=t.begin();int y=it->se;t.erase(it);
for(auto v:g[x]) tree2::vis[v]=1,tree3::f[v][0]=(tree3::Node){v,v,tree2::dis[v]<<1},tree3::f[v][1]=(tree3::Node){0,0,0};
for(auto v:g[y]) tree2::vis[v]=1,tree3::f[v][1]=(tree3::Node){v,v,tree2::dis[v]<<1},tree3::f[v][0]=(tree3::Node){0,0,0};
for(auto v:g[x]) g[y].pb(v);
t.insert(mp(g[y].size(),y));
tree2::build(g[y]);
for(auto v:g[y]) tree2::vis[v]=0;
}
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(vis[v]) continue;
rt=0,psum=siz[v];
findrt(v,0),findrt(rt,0);
solve(rt);
}
}
inline void work(){
maxx[rt=0]=INF,psum=n;
findrt(1,0);findrt(rt,0);
solve(rt);
}
}
namespace tree2{
struct Stack{
int s[N],t;
inline void clear(){s[t=0]=0;}
Stack(){clear();}
inline void push(int x){s[++t]=x;}
inline void pop(){--t;}
inline int ttop(){return s[t-1];}
inline int top(){return s[t];}
inline bool empty(){return !t;}
};
Edge e[N<<1];
int h[N],etot;
inline void add_edge(int u,int v,ll w){e[++etot]=(Edge){v,w,h[u]};h[u]=etot;}
inline void readedge(){for(int i=1;isiz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf,id[u]=++dfs_clock;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]] a){
Stack st;
std::sort(a.begin(),a.end(),cmp);
st.push(1);if(!vis[1]) tree3::f[1][0]=tree3::f[1][1]=(tree3::Node){0,0,0};
for(int i=0,lim=a.size();i1&&id[t]siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]