luoguU60884 【模板】动态点分治套线段树

题目连接：https://www.luogu.org/problemnew/show/U60884

题意：有N个点，标号为1∼N，用N−1条双向带权通道连接，保证任意两个点能互相到达。

Q次询问，问从编号为x的点到达标号L∼R的点其中一个点的最小距离是多少。

说明 :N,Q<1e5，边权<1e4;

思路：不难想到点分树，保存每个点到其“负责”的点的距离，这样的话可以套线段树，线段树保存其他点到点的距离。

但是，点分树上有个需要解决的问题是：如果x顺着点分树向父亲走，那么在父亲保存的线段树中要除去从儿子上来的那一部分（否则的话，不是简单路径，求出来的可能会错）。想了一下这里很难实现，因为是取min操作，所以线段树上二分估计也不行。所以卡住了。

然后求问群友，群友提到了虚树，我觉得此题的数据需要没法实现。后面猛地想通，我们不需要考虑“回走”这种情况，因为我们求的是最小距离，而非简单路径肯定是没有简单路径优的。那么就是果然如标题所说，是个板子题了。

代码实现：点分树+线段树+树剖求LCA。

点分树：点分治的过程中新建的树，树根是第一次找到是重心，每一层的重心与上一层的重心连边得到点分树。

点分树里保存的是自己作为重心时，会“负责”的点，即此时还没有vis过的，且与自己连通的点。

所有经过“x”到达的点，保存在了两部分里：一是x在点分树里保存的信息。二是x在点分树的祖先里保存的信息(这一部分保留了x向上传递是信息，所以大部分题要把这里除去，此题由于是取min，可以不考虑)。

求LCA：开始用了ST表，但是感觉空间耗费太大，就改为了树剖，跑起来还挺快。

#include<bits/stdc++.h>

#define rep(i,w,v) for(int i=w;i<=v;i++)

#define FOR() for(int i=Laxt[u];i;i=Next[i])

using namespace std;

#define ll long long

#define RG register

#define maxn 100010

#define maxm 200010

#define inf 1e9

int fa[maxn],n,cnt;

int dep[maxn];bool vis[maxn];

int Laxt[maxn],Next[maxm],To[maxm],Len[maxm];

int siz[maxn],fcy[maxn],hson[maxn],Top[maxn];

void add(int u,int v,int len)

{

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=len;

}

void dfs1(int u,int ff)

{

    fa[u]=ff; siz[u]=;

    dep[u]=dep[ff]+;

    FOR(){

        int v=To[i];if(v==ff)continue;

        fcy[v]=fcy[u]+Len[i];

        dfs1(v,u); siz[u]+=siz[v];

        if(siz[v]>siz[hson[u]]) hson[u]=v;

    }

}

void dfs2(int u,int tp)

{

    Top[u]=tp;

    if(hson[u])dfs2(hson[u],tp);

    FOR()

        if(To[i]!=fa[u]&&To[i]!=hson[u])

            dfs2(To[i],To[i]);

}

int LCA(int u,int v)

{

    while(Top[u]^Top[v]) dep[Top[u]]<dep[Top[v]]?v=fa[Top[v]]:u=fa[Top[u]];

    return dep[u]<dep[v]?u:v;

}

int Dis(int u,int v){return fcy[u]+fcy[v]-*fcy[LCA(u,v)];}

int Fa[maxn],Size,root,mx,rt[maxn];

void Getroot(int u,int ff)

{

    siz[u]=;int ret=;

    FOR(){

        int v=To[i];if(v==ff||vis[v])continue;

        Getroot(v,u);siz[u]+=siz[v];

        ret=max(ret,siz[v]);

    }

    ret=max(ret,Size-siz[u]);

    if(ret<mx) mx=ret,root=u;

}

void DFS(int u,int ff)

{

    vis[u]=true;Fa[u]=ff;

    FOR(){

        int v=To[i];if(vis[v])continue;

        mx=Size=siz[v];

        Getroot(v,u);

        DFS(root,u);

    }

}

struct in{ int l,r,mn; }s[maxn<<]; int tot;

void modify(int &Now,int L,int R,int pos,int val)

{

    if(!Now){Now=++tot; s[tot].mn=inf;}

    s[Now].mn=min(s[Now].mn,val);

    if(L==R) return; int Mid=(L+R)>>;

    if(pos<=Mid) modify(s[Now].l,L,Mid,pos,val);

    else modify(s[Now].r,Mid+,R,pos,val);

}

int query(int Now,int L,int R,int l,int r)

{

    if(!Now) return inf;

    if(l<=L&&r>=R) return s[Now].mn;

    int Mid=(L+R)>>,res=inf;

    if(l<=Mid) res=min(res,query(s[Now].l,L,Mid,l,r));

    if(r>Mid) res=min(res,query(s[Now].r,Mid+,R,l,r));

    return res;

}

void Modify(int x)

{

    modify(rt[x],,n,x,);

    for(int i=x;Fa[i];i=Fa[i]){

        int dis=Dis(x,Fa[i]);

        modify(rt[Fa[i]],,n,x,dis);

    }

}

int Query(int x,int L,int R)

{

    int res=query(rt[x],,n,L,R);

    for(int i=x;Fa[i];i=Fa[i])

    {

        int dis=Dis(x,Fa[i]);

        res=min(res,dis+query(rt[Fa[i]],,n,L,R));

    }

    return res;

}

int main()

{

    int Q,u,v,len;

    scanf("%d",&n);

    rep(i,,n-){

        scanf("%d%d%d",&u,&v,&len);

        add(u,v,len); add(v,u,len);

    }

    dfs1(,); dfs2(,);

    Size=mx=n;

    Getroot(,); DFS(root,);

    rep(i,,n) Modify(i);

    int ans=,l,r,x;

    scanf("%d",&Q);

    while(Q--){

        scanf("%d%d%d",&l,&r,&x);

        printf("%d\n",Query(x,l,r));

    }

    return ;

}

巴特西

luoguU60884 【模板】动态点分治套线段树

最新文章

热门文章