题解：P14622 [2019 KAIST RUN Fall] Wind of Change

· · 题解

最值全部都被松掉了。

对第二棵树建出点分树，则 dis2(u,v)=\min_{u,v\in subtree(g)}dis2(u,g)+dis2(v,g)。

对第一颗树进行点分治。设分治重心为 rt，对于每个点暴力跳点分树祖先更新 \min_{u\in subtree(g)}dis1(u,rt)+dis2(u,g) 的最小值和次小值以及对应点（不能是同一个点），然后再暴力求答案即可。

由于点分树深度为 O(\log n)，时间复杂度 O(n\log^2n)。

:::success[点击查看参考代码]

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l),qwp=(r);i<=qwp;i++)
#define per(i,r,l) for(int i=(r),qwp=(l);i>=qwp;i--)
#define pb push_back
#define clr clear
using namespace std;
namespace ax_by_c{
typedef long long ll;
typedef pair<ll,int> P;
constexpr ll llinf=3e18;
constexpr int N=250005;
constexpr int LN=20;
int n,asz,sz[N],rt,mnw,zfa[N],lt[N][LN],de[N],zz[N][LN];ll ans[N],des[N],zw[N],ww[N][LN];bool rem[N];P _mn[N],_se[N];
struct Edge{int v,w;};vector<Edge>g[2][N];vector<int>nds;
void dfs1(int u,int fa){sz[u]=1;int w=0;for(auto e:g[1][u])if(e.v!=fa&&!rem[e.v])dfs1(e.v,u),sz[u]+=sz[e.v],w=max(w,sz[e.v]);w=max(w,asz-sz[u]);if(w<mnw)rt=u,mnw=w;}
int bld(int pp,int tt){asz=tt,mnw=n,dfs1(pp,0),pp=rt,dfs1(pp,0),rem[pp]=1;for(auto e:g[1][pp])if(!rem[e.v])zfa[bld(e.v,sz[e.v])]=pp;return pp;}
void ddfs(int u){for(auto e:g[1][u])if(e.v!=lt[u][0])lt[e.v][0]=u,de[e.v]=de[u]+1,des[e.v]=des[u]+e.w,ddfs(e.v);}
int kfa(int u,int k){per(j,LN-1,0)if(k&(1<<j))u=lt[u][j];return u;}
int lca(int x,int y){if(de[x]>de[y])swap(x,y);y=kfa(y,de[y]-de[x]);per(j,LN-1,0)if(lt[x][j]!=lt[y][j])x=lt[x][j],y=lt[y][j];return (x==y)?(x):(lt[x][0]);}
ll gws(int x,int y){return des[x]+des[y]-des[lca(x,y)]*2;}
void dfs2(int u,int fa){sz[u]=1;int w=0;for(auto e:g[0][u])if(e.v!=fa&&!rem[e.v])dfs2(e.v,u),sz[u]+=sz[e.v],w=max(w,sz[e.v]);w=max(w,asz-sz[u]);if(w<mnw)rt=u,mnw=w;}
void _pd(int u,P z){if(_mn[u]>z)_se[u]=_mn[u],_mn[u]=z;else if(_se[u]>z)_se[u]=z;}
void upd(int u,ll z){rep(i,1,LN-1){if(!zz[u][i])break;_pd(zz[u][i],{ww[u][i]+z,u});}}
void dfs3(int u,int fa){nds.pb(u),sz[u]=1;for(auto e:g[0][u])if(e.v!=fa&&!rem[e.v])zw[e.v]=zw[u]+e.w,dfs3(e.v,u),sz[u]+=sz[e.v];}
ll tak(int u,ll z){ll res=llinf;rep(i,1,LN-1){if(!zz[u][i])break;P t=_mn[zz[u][i]];if(t.second==u)t=_se[zz[u][i]];res=min(res,t.first+ww[u][i]+z);}return res;}
void clr(int u){rep(i,1,LN-1){if(!zz[u][i])break;_mn[zz[u][i]]=_se[zz[u][i]]={llinf,0};}}
void dfz(int pp,int tt){
    asz=tt,mnw=n,dfs2(pp,0),pp=rt,zw[pp]=0;
    nds.clr(),dfs3(pp,0);for(auto u:nds)upd(u,zw[u]);for(auto u:nds)ans[u]=min(ans[u],tak(u,zw[u]));for(auto u:nds)clr(u);
    rem[pp]=1;for(auto e:g[0][pp])if(!rem[e.v])dfz(e.v,sz[e.v]);
}
void main(){
    scanf("%d",&n);
    rep(_,0,1)rep(i,1,n-1){int x,y,w;scanf("%d%d%d",&x,&y,&w),g[_][x].pb({y,w}),g[_][y].pb({x,w});}
    rt=bld(1,n);
    ddfs(1);rep(j,1,LN-1)rep(i,1,n)lt[i][j]=lt[lt[i][j-1]][j-1];
    rep(i,1,n){int u=i,idx=0;while(u)idx++,zz[i][idx]=u,ww[i][idx]=gws(i,u),u=zfa[u];}
    rep(i,1,n)ans[i]=llinf,rem[i]=0,_mn[i]=_se[i]={llinf,0};
    dfz(1,n);
    rep(i,1,n)printf("%lld\n",ans[i]);
}
}
int main(){
    // auto ST=chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
    // freopen("frame.in","r",stdin);
    // freopen("frame.out","w",stdout);
    ax_by_c::main();
    // auto ED=chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
    // cerr<<"TIME:"<<ED-ST<<'\n';
    return 0;
}
/*
g++ -std=c++14 -O2 -Wall -Wextra "-Wl,--stack=200000000" frame.cpp -o frame.exe
frame.exe
*/

:::