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

 

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

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

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

                                   

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

具体做法的话，首先找到环上的点并标记，然后从每一个环上的点开始往外拓展非环上的点，并把每一个拓展出来的点的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;
}