简要题意：给你三棵树，二元组 $(x,y)$ 的贡献是 $x,y$ 在三棵树上最短路径经过的边边权之和，求贡献最高的二元组 $(x,y)$ 所产生的贡献。
考虑对第一棵树边分治，注意到边分治的好处就是直接将第一棵树上 $(x,y)$ 的贡献由原来连在一起的变成相对 $x ,y$ 独立的了。
按照”CTSC 2018 暴力写挂” 学来的技巧，对第二棵树建虚树，然后就可以再虚树上面继续做了。但是这个时候还没有拆开第三个树的贡献。对比”CTSC 2018 暴力写挂”，可以发现多了个树，但是边权是非负的。
考虑到，对于一棵树，如果点集 $S_0$ 中最远点对为 $(x_0,y_0)$，在 $S_1$ 中最远点对为 $(x_1,y_1)$，那么在 $S_0\cup S_1$ 中，端点在 $x_0,x_1,y_0,y_1$ 中的路径仍然是最远点对。证明的话可以考虑证得距离 $x_0$ 最远的属于 $S_1$ 的点一定是 $y_0,y_1$ 其中之一，同理可得 $x_1,y_0,y_1$ 。
这样子合并的话只需要考虑 $O(1)$ 种情况了，实现时需要注意合并最长链的细节。
代码看看就好。
namespace tree3 { // {{{
const int LogN=20;
ll dis[N];
int m,tim,fir[N],dfn[N],dep[N],_log[N<<1],st[N<<1][LogN];
std::vector <pil> son[N];
inline void addedge(int u,int v,ll w) {son[u].pb(mkp(v,w)),son[v].pb(mkp(u,w));}
/*--------------------------------------------------------------------------------*/
// {{{ init
#define chklca(x,y) (dep[x]>dep[y]?y:x)
void dfs(int u,int lst) {
dfn[u]=++tim,st[fir[u]=++m][0]=u,dep[u]=dep[lst]+1;
for(pil v:son[u]) if(v.fi!=lst) dis[v.fi]=dis[u]+v.se,dfs(v.fi,u),st[++m][0]=u;
}
void init() {
dfs(1,0),_log[0]=-1;
lep(j,1,19) { const int t=1<<j,k=1<<(j-1); lep(i,1,m) if(i+t-1<=m) {
st[i][j]=chklca(st[i][j-1],st[i+k][j-1]);
}}
lep(i,1,m) _log[i]=_log[i>>1]+1;
}
inline int lca(int x,int y) {
x=fir[x],y=fir[y]; if(x>y) swap(x,y);
int k=_log[y-x+1];
return chklca(st[x][k],st[y-(1<<k)+1][k]);
}
// }}}
// {{{ tool
inline ll dist(int x,int y) {return dis[x]+dis[y]-(dis[lca(x,y)]<<1);}
// }}}
} // }}}
namespace tree2 { // {{{
const int LogN=20;
int tag[N];
ll extraval,val[N],dis[N];
// {{{ struct chain
inline ll calc(const pii &t) {return tree3::dist(t.fi,t.se)+val[t.fi]+val[t.se];}
inline pii chkgod(const pii &x,const pii &y) {return calc(x)<calc(y)?y:x;}
inline pii merge(const pii &t0,const pii &t1) {
pii r0=chkgod(mkp(t0.fi,t1.fi),mkp(t0.fi,t1.se));
pii r1=chkgod(mkp(t0.se,t1.fi),mkp(t0.se,t1.se));
return chkgod(chkgod(t0,t1),chkgod(r0,r1));
}
inline pii answer(const pii &t0,const pii &t1) {
pii r0=chkgod(mkp(t0.fi,t1.fi),mkp(t0.fi,t1.se));
pii r1=chkgod(mkp(t0.se,t1.fi),mkp(t0.se,t1.se));
return chkgod(r0,r1);
}
// }}}
int top,sta[N];
std::vector <int> Gv[N];
int m,tim,fir[N],dfn[N],dep[N],_log[N<<1],st[N<<1][LogN];
std::vector <pil> son[N];
inline void addedge(int u,int v,ll w) {son[u].pb(mkp(v,w)),son[v].pb(mkp(u,w));}
/*--------------------------------------------------------------------------------*/
// {{{ init
#define chklca(x,y) (dep[x]>dep[y]?y:x)
void dfs(int u,int lst) {
dfn[u]=++tim,st[fir[u]=++m][0]=u,dep[u]=dep[lst]+1;
for(pil v:son[u]) if(v.fi!=lst) dis[v.fi]=dis[u]+v.se,dfs(v.fi,u),st[++m][0]=u;
}
void init() {
dfs(1,0),_log[0]=-1;
lep(j,1,19) { const int t=1<<j,k=1<<(j-1); lep(i,1,m) if(i+t-1<=m) {
st[i][j]=chklca(st[i][j-1],st[i+k][j-1]);
}}
lep(i,1,m) _log[i]=_log[i>>1]+1;
}
inline int lca(int x,int y) {
x=fir[x],y=fir[y]; if(x>y) swap(x,y);
int k=_log[y-x+1];
return chklca(st[x][k],st[y-(1<<k)+1][k]);
}
// }}}
// {{{ build
void clear(int u) {
for(int v:Gv[u]) clear(v);
tag[u]=val[u]=0,Gv[u].clear();
}
void build(std::vector <int> node) {
sta[top=1]=1; int u; rep(i,node.size()-1,0) if(u=node[i],u!=1) {
int l=lca(u,sta[top]);
if(l!=sta[top]) {
while(dfn[l]<dfn[sta[top-1]]) Gv[sta[top-1]].pb(sta[top]),--top;
if(dfn[l]!=dfn[sta[top-1]]) Gv[l].pb(sta[top]),sta[top]=l;
else Gv[l].pb(sta[top--]);
}
sta[++top]=u;
}
lep(i,2,top) Gv[sta[i-1]].pb(sta[i]);
}
// }}}
// {{{ solve
std::pair <pii,pii> dp(int u) {
pii c1=mkp((tag[u]==1)?u:0,0);
pii c2=mkp((tag[u]==2)?u:0,0);
for(int v:Gv[u]) {
std::pair <pii,pii> tmp=dp(v);
chkmax(ans,calc(answer(c1,tmp.se))+extraval-(dis[u]<<1)),c1=merge(c1,tmp.fi);
chkmax(ans,calc(answer(c2,tmp.fi))+extraval-(dis[u]<<1)),c2=merge(c2,tmp.se);
}
return mkp(c1,c2);
}
// }}}
} // }}}
namespace tree1 { // {{{
const int _N=N<<2;
int rt,lstn,nowmax,vis[_N],siz[_N];
std::vector <pil> nodedis[_N<<1];
int cnt=1,head[_N];
std::vector <pil> son[_N];
struct Edge{int nxt,to; ll val;} G[_N<<1];
inline void addedge (int u,int v,ll w) {G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;}
/*--------------------------------------------------------------------------------*/
void check(int u,int lst) {
printf("visit %d,%d\n",u,lst);
for(int v,i=head[u];i;i=G[i].nxt) if(v=G[i].to,v!=lst&&!vis[i>>1]) check(v,u);
}
// {{{ init
void dfs(int u,int lst) {
for(int v,i=head[u];i;i=G[i].nxt)
if(v=G[i].to,v!=lst) dfs(v,u),son[u].pb(mkp(v,G[i].val));
}
void rebuild() {
dfs(1,0),memset(head,0,sizeof(head)),cnt=1; lep(i,1,n) {
int now=son[i].size()-1;
if(now>1) {
++n,addedge(i,n,0),addedge(n,i,0);
++n,addedge(i,n,0),addedge(n,i,0);
lep(j,0,now) (j&1)?son[n].pb(son[i][j]):son[n-1].pb(son[i][j]);
} else for(pil j:son[i]) addedge(i,j.fi,j.se),addedge(j.fi,i,j.se);
}
}
// }}}
// {{{ solve
void getrt(int u,int lst,int allsiz) {
siz[u]=1;
for(int v,i=head[u];i;i=G[i].nxt) if(v=G[i].to,v!=lst&&!vis[i>>1]) {
getrt(v,u,allsiz),siz[u]+=siz[v];
int tmpmax=max(siz[v],allsiz-siz[v]);
if(tmpmax<nowmax) nowmax=tmpmax,rt=i;
}
}
void getdis(int u,int lst,ll len) {
if(u<=lstn) nodedis[rt].pb(mkp(u,len));
for(int v,i=head[u];i;i=G[i].nxt) if(v=G[i].to,v!=lst&&!vis[i>>1]) getdis(v,u,len+G[i].val);
}
std::vector <int> solve(int u,int allsiz) {
std::vector <int> node(0);
nowmax=inf,getrt(u,0,allsiz);
if(nowmax==inf) return (u>lstn?void():node.pb(u)),node;
int now=rt,nxt=siz[G[rt].to],p1=G[now].to,p2=G[now^1].to;
vis[rt>>1]=true;
getdis(p1,p2,0),getdis(p2,p1,0);
std::vector <int> son1=solve(G[now].to,nxt);
std::vector <int> son2=solve(G[now^1].to,allsiz-nxt);
for(int v:son1) tree2::tag[v]=1;
for(int v:son2) tree2::tag[v]=2;
// merge
while(son1.size()&&son2.size())
(tree2::dfn[son1.back()]<tree2::dfn[son2.back()])?
(node.pb(son1.back()),son1.pp()):(node.pb(son2.back()),son2.pp());
while(son1.size()) node.pb(son1.back()),son1.pp();
while(son2.size()) node.pb(son2.back()),son2.pp();
std::reverse(node.begin(),node.end());
// build virtual tree to get answer
tree2::extraval=G[now].val,tree2::build(node);
for(pil ele:nodedis[now]) tree2::val[ele.fi]=ele.se+tree2::dis[ele.fi];
tree2::dp(1),tree2::clear(1);
return node;
}
// }}}
} // }}}
int u,v; ll w; int main() {
IN(n),tree1::lstn=n;
lep(i,2,n) IN(u,v),IN(w),tree1::addedge(u,v,w),tree1::addedge(v,u,w);
lep(i,2,n) IN(u,v),IN(w),tree2::addedge(u,v,w);
lep(i,2,n) IN(u,v),IN(w),tree3::addedge(u,v,w);
tree1::rebuild(),tree2::init(),tree3::init();
tree1::solve(1,n);
printf("%lld\n",ans);
return 0;
}
0 条评论