题解：P12703 [KOI 2022 Round 2] 外环路

· · 题解

这题的图是 Halin Graph，树宽为 3，可以构造 Halin Graph 树分解（code1），然后用逛公园一题树分解的做法解决（code2），复杂度 O(n\log n+q)。

下面讲一点更 oi 的做法。

画图会发现这是一张平面图，由最外面的一个环（连起了所有叶子）和中间的一棵树组成。

对于这题，可以对树三度化，进行边分治。

对于树上被切开的两个连通块，两部分之间最多有三条边相连（环上两条边，一条树边）。

对于 O(1) 个这几条边上的点，作为起点跑一遍最短路，然后把当前的询问答案都 chkmin 一下。

跨越两边的询问不必再递归，在同一边的询问递归下去，每个询问最多被递归 \log 次。

复杂度 O(n\log^2 n+q\log n)。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 400005
#define inf 0x3f3f3f3f3f3f3f3f

int n,nn,m,res[maxn];
int qu[maxn],qv[maxn];
int fa[maxn];
vector<pii>G[maxn];

struct edge{
    int to,nxt,w;
}e[maxn<<1];
int tot=1,head[maxn];
void adde(int u,int v,int w){
    e[++tot]=(edge){v,head[u],w};
    head[u]=tot;
}
void add(int u,int v,int w){
    adde(u,v,w);
    adde(v,u,w);
}

void rebuild(int u,int pa){
    int lst=u;
    for(auto it:G[u]){
        int v=it.fi,w=it.se; 
        if(v==pa)continue;
        rebuild(v,u);
        add(lst,++nn,0),add(nn,v,w);
        lst=nn;
    }
}

vector<pii>go[maxn];

#define iter(i,u,v,w) for(int i=head[u],v=e[i].to,w=e[i].w;i;i=e[i].nxt,v=e[i].to,w=e[i].w)

int allsz,mn,id,sz[maxn];
bool vis[maxn<<1];
void gete(int u,int pa){
    sz[u]=1;
    iter(i,u,v,w){
        if(v==pa || vis[i])continue;
        gete(v,u); sz[u]+=sz[v];
        if(mn>max(sz[v],allsz-sz[v])) mn=max(sz[v],allsz-sz[v]),id=i;
    }
}

int col[maxn];
int st[maxn],top;

namespace D{

struct edge{
    int to,nxt,w;
}e[maxn<<1];
int tot,head[maxn];
void adde(int u,int v,int w){
    e[++tot]=(edge){v,head[u],w};
    head[u]=tot;
}
bool vis[maxn];
void dij(int u,int*dis){
    For(i,1,top) vis[st[i]]=0,dis[st[i]]=inf;
    dis[u]=0;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push(mkp(0,u));
    while(q.size()){
        int u=q.top().se;q.pop();
        if(vis[u])continue; vis[u]=1;
        iter(i,u,v,w){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(mkp(dis[v],v));
            }
        }
    }
}

}

void color(int u,int pa,int c){
    col[u]=c;
    st[++top]=u;
    iter(i,u,v,w)if(!vis[i]&&v!=pa)color(v,u,c);
}

pii tmp[999]; int len,tw[999];
int dis[9][maxn];
void clear(){
    For(i,1,top){
        int u=st[i];
        col[u]=0; D::head[u]=0;
    }top=0; D::tot=0; len=0;
}

void solve(int u,vi qs){
    if(allsz==1||!qs.size())return;
    mn=inf,gete(u,0);
    int x=e[id].to,y=e[id^1].to;
    vis[id]=vis[id^1]=1;
    vi qx,qy;
    color(x,0,1);
    color(y,0,2);
    For(i,1,top){
        int u=st[i];
        iter(i,u,v,w){
            if(!col[v])continue;
            D::adde(u,v,w);
            if(col[u]==1&&col[v]==2) tmp[++len]=mkp(u,v),tw[len]=w,assert(len<=3);
        }
        for(auto it:go[u]){
            int v=it.fi,w=it.se;
            if(!col[v])continue;
            D::adde(u,v,w);
            if(col[u]==1&&col[v]==2) tmp[++len]=mkp(u,v),tw[len]=w,assert(len<=3);
        }
    }
    assert(len<=3);
    For(i,1,len){
        D::dij(tmp[i].fi,dis[i*2-1]);
        D::dij(tmp[i].se,dis[i*2]);
    }
    for(auto it:qs){
        int u=qu[it],v=qv[it];
        if(col[u]>col[v])swap(u,v);
        if(col[u]!=col[v]){
            For(i,1,len){
                res[it]=min(res[it],dis[i*2-1][u]+dis[i*2][v]+tw[i]);
            }
        }else{
            if(col[u]==1){
                For(i,1,len) res[it]=min(res[it],dis[i*2-1][u]+dis[i*2-1][v]);
                qx.pb(it);
            }else{
                For(i,1,len) res[it]=min(res[it],dis[i*2][u]+dis[i*2][v]);
                qy.pb(it);
            }
        }
    }
    clear();
    allsz=sz[x],solve(x,qx);
    allsz=sz[y],solve(y,qy);
}

int leaf[maxn],lcnt;

signed main()
{
    n=read();nn=n;
    For(i,2,n){
        fa[i]=read(); int w=read();
        G[i].pb(mkp(fa[i],w));
        G[fa[i]].pb(mkp(i,w));
    }
    For(i,1,n) if(G[i].size()==1) leaf[lcnt++]=i;
    For(i,0,lcnt-1){
        int u=leaf[i],v=leaf[(i+1)%lcnt];
        int w=read();
        go[u].pb(mkp(v,w)),go[v].pb(mkp(u,w));
    }
    rebuild(1,0);
    allsz=nn;
    vi orz;
    m=read();
    For(i,1,m){
        qu[i]=read(),qv[i]=read();
        orz.pb(i);
        res[i]=inf;
    }
    solve(1,orz);
    For(i,1,m){
        printf("%lld\n",res[i]);
    }
    return 0;
}