欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 6393 2018HDU多校赛 第七场 Traffic Network in Numazu(树链剖分 + 树状数组)

程序员文章站 2022-06-09 19:28:20
...

HDU 6393 2018HDU多校赛 第七场 Traffic Network in Numazu(树链剖分 + 树状数组)HDU 6393 2018HDU多校赛 第七场 Traffic Network in Numazu(树链剖分 + 树状数组)

 

大致题意:给你一个含有一个环的树,即n个点n条边的图,然后动态修改每一条边的边权,同时动态询问任意两点之间的最短距离。

非常裸的一道图论+数据结构题。首先,我们考虑如果没有环的情况下,那就是一个显然的树链剖分+线段树/树状数组的题目,但是现在有一个环就变得不一样了。但是这种题目显然是要把树变成环的,于是我选择环上的一条边剪断,选择环上任意一个点为根,这样就可以构成一棵树了。

具体来说,我把树分为两个部分,一个是环上的点,一个是非环上的点。对于环上的点,我们维护一个树状数组0,表示环内各个点不绕圈的情况下相互到达的距离。对于非环上的点,我们维护一个树状数组1,表示所有非环上的点距离其最近的一个环上的点的距离。这样,对于任意一个查询(x,y),首先判断距离两个点最近的环上点是否是同一个点,如果是的话,说明两个点之间的最短路并没有经过一条环上的边,因此我们直接用树状数组1内,x、y以及其lca对其最近的环上点的距离,求和作差即可。对于两个点最近的环上点不是同一个点的话,那么我们要把最短路分为三个部分,第一是x与其最近的环上点的距离,第二是y与其最近的环上点的距离,第三是两个环上点之间的距离。具体来说可以见下图。

                                    HDU 6393 2018HDU多校赛 第七场 Traffic Network in Numazu(树链剖分 + 树状数组)

其中黑色的点表示环上的点,那么相当于把黑色的点当作整个树的主心骨,然后对于非环上的点,树状数组就保存其距离最近的黑色的点的距离。然后黑色的点之间的距离是 树状数组中两点的距离 和 转一圈之后二者的距离 的最小值。

具体做法的话,首先找到环上的点并标记,然后从每一个环上的点开始往外拓展非环上的点,并把每一个拓展出来的点的id标记为对应开始拓展点的编号。拓展的同时,维护树状数组。之后,再拓展环上的点,对每一个环上的点重标号,记录为hid,维护树状数组。然后查询和修改的时候按照之前所说的修改即可。具体见代码:

#include<bits/stdc++.h>
#define LL long long
#define clr(x,n) memset(x,0,sizeof(x[0])*(n+5))
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)

using namespace std;

const int N = 1e5+10;

namespace IO
{
    const int len=2e7;char buf[len];int sz,p;

    void begin(){p=0;sz=fread(buf,1,len,stdin);}

    inline bool read(LL &x)
    {
        if (p==sz)return 0;int f=1,d=0;char s=buf[p++];
        while(s<'0'||s>'9'&&p<sz){if(s=='-') f=-1;s=buf[p++];}
        while(s>='0'&&s<='9'&&p<sz){d=d*10+s-'0';s=buf[p++];}
        x=f*d; return p!=sz;
    }
    inline void writeln(LL x)
    {
        if(x==0){putchar('0');putchar('\n');return;}
        if(x<0)putchar('-'),x=-x;int len=0,buf[20];
        while(x)buf[len++]=x%10,x/=10;int i=len-1;
        while (i>=0){putchar(buf[i--]+'0');}putchar('\n');return;
    }
}


int lc[N],rc[N],top[N],size[N],son[N],fa[N],dep[N];
int ls[N],on[N],f[N],id[N],hid[N],num;LL n,m,tot,e;
struct Edge{int x,y;LL w,nxt;} g[N<<1];

inline void dfs1(int u,int d,int f)
{
    son[u]=0; dep[u]=d; size[u]=1;
    for(int i=ls[u];i;i=g[i].nxt)
        if (g[i].y!=f)
        {
            fa[g[i].y]=u;
            dfs1(g[i].y,d+1,u);
            size[u]+=size[g[i].y];
            if (size[g[i].y]>size[son[u]]) son[u]=g[i].y;
        }
}

inline void dfs2(int u,int f)
{
    top[u]=f; lc[u]=++num;
    if (son[u]) dfs2(son[u],f);
    for(int i=ls[u];i;i=g[i].nxt)
        if (g[i].y!=son[u]&&g[i].y!=fa[u]) dfs2(g[i].y,g[i].y);
    rc[u]=num;
}

inline int LCA(int u,int v)
{
    int tp1=top[u],tp2=top[v];
    while (tp1!=tp2)
    {
        if (dep[tp1]<dep[tp2]) swap(tp1,tp2),swap(u,v);
        u=fa[tp1]; tp1=top[u];
    }
    if (dep[u]>dep[v]) swap(u,v);
    return u;
}

inline void addedge(int x,int y,int w){g[++e]=Edge{x,y,w,ls[x]};ls[x]=e;}

struct BinaryIndexedTree
{
    LL c[N];
    inline LL lowbit(int x){return x&-x;}
    inline void init(int n){memset(c,0,sizeof(c));}
    inline void update(int x,LL k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
    inline LL getsum(int x){LL ans=0;for(;x>0;x-=lowbit(x))ans+=c[x];return ans;}

} BIT[2];

bool dfs(int x,int father,int y)
{
    for(int i=ls[x];i;i=g[i].nxt)
    {
        if (g[i].y==father) continue;
        fa[g[i].y]=x;
        if (g[i].y==y)
        {
            on[y]=1;
            for(int j=x;j!=0;j=fa[j])
                on[j]=1; return 1;
        }
        if (dfs(g[i].y,x,y)) return 1;
    }
}

inline int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

inline void expand(int x,int fa,int ff)                //对环上的每一个点拓展
{
    id[x]=ff;                                    //id标记为对应的起点,即距离最近的环上点
    for(int i=ls[x];i;i=g[i].nxt)
    {
        if (on[g[i].y]||g[i].y==fa) continue;            //只走非环上的点
        BIT[1].update(lc[g[i].y],g[i].w);                //维护树状数组
        BIT[1].update(rc[g[i].y]+1,-g[i].w);
        expand(g[i].y,x,ff);
    }
}

inline void circle(int x,int fa,LL dist)                //对环上的点重标号,并且维护树状数组
{
    hid[x]=++tot;
    for(int i=ls[x];i;i=g[i].nxt)
    {
        if (g[i].y==fa||!on[g[i].y]) continue;
        BIT[0].update(tot+1,dist+g[i].w);
        BIT[0].update(tot+2,-dist-g[i].w);
        circle(g[i].y,x,dist+g[i].w);
    }
}

int main()
{
    //file(xxxx);
    LL T; IO::begin();
    IO::read(T);
    while(T--)
    {
        int root=1;LL sum=0;
        BIT[0].init(n); BIT[1].init(n);
        clr(ls,n); clr(lc,n); clr(son,n);
        clr(rc,n); clr(fa,n); clr(size,n);
        clr(dep,n); clr(top,n); clr(on,n);
        clr(hid,n); clr(id,n); e=num=tot=0;
        IO::read(n); IO::read(m);
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=n;i++)
        {
            LL x,y,w; IO::read(x);
            IO::read(y); IO::read(w);
            if (find(x)!=find(y))                        //如果二者不连通,直接加
            {
                f[find(x)]=find(y);
                addedge(x,y,w);
                addedge(y,x,w);
            } else                                //如果已经连通,说明找到了环,记下root
            {                                        //同时dfs遍历环上的点,标记为在环上
                sum=w,dfs(root=x,0,y);    
                g[++e]=Edge{x,y,w,0};
                g[++e]=Edge{y,x,w,0};
            }
        }
        dfs1(root,0,0);                            //树链剖分
        dfs2(root,root);                            //标记每个点及其子树的编号范围lc和rc
        for(int i=1;i<=n;i++)
            if (on[i]) expand(i,fa[i],i);            //对于每一个环上的点进行拓展
        circle(root,0,0); sum+=BIT[0].getsum(tot);    //重标号环上的点
        while(m--)
        {
            LL op,x,y; IO::read(op);
            IO::read(x); IO::read(y);
            if (op==0)
            {
                x<<=1;
                int a=g[x].x,b=g[x].y;
                if (dep[a]>dep[b]) swap(a,b);
                if (on[a]==1&&on[b]==1)               //若两个点都在换上,那么修改树状数组0
                {
                    if (dep[b]-dep[a]<=1) BIT[0].update(hid[b],y-g[x].w);
                    sum+=y-g[x].w;
                } else
                {                                       //否则修改树状数组1
                    BIT[1].update(lc[b],y-g[x].w);
                    BIT[1].update(rc[b]+1,g[x].w-y);
                }
                g[x].w=y;
            } else
            {
                if (dep[x]>dep[y]) swap(x,y);
                if (id[x]!=id[y])                //距离最近的环上点不相同,则分为三部分
                {
                    int l=min(hid[id[x]],hid[id[y]]);
                    int r=max(hid[id[x]],hid[id[y]]);
                    LL tmp=BIT[0].getsum(r)-BIT[0].getsum(l);    //换上点之间的距离
                    LL a=on[x]?0:BIT[1].getsum(lc[x]);       //x距离其最近环上点的距离
                    LL b=on[y]?0:BIT[1].getsum(lc[y]);        //y距离其最近的环上点的距离
                    IO::writeln(a+b+min(tmp,sum-tmp));
                } else
                {                                        //相同则是x、y和lca求和作差
                    int lca=LCA(x,y);
                    LL a=on[x]?0:BIT[1].getsum(lc[x]);
                    LL c=on[lca]?0:BIT[1].getsum(lc[lca]);
                    IO::writeln(a+BIT[1].getsum(lc[y])-2LL*c);
                }
            }
        }
    }
    return 0;
}