标签归档:DFS序

[hdu6393][多校第七场]Traffic Network in Numazu

Link

求一个环套树上两点的最短路,支持边权修改。

Solution

找出环来,拆开,用树状数组维护环拆成的链的前缀和,求最短距离的话两种情况枚举一下。
对于环上的森林,就每棵树都用树状数组维护DFS序,再加上任意一种LCA方法,就可以求出了。

Tips

  1. 倍增LCA需要判一下当前第$2^k$祖先是否存在!
  2. 注意应该用的数据类型,又爆int了,造了链的数据才拍出来。

Code

const int XN=1e5+11,XLOGN=17;

int lg2[XN];

long long Sum(std::vector<long long> const& bit,int pos) {
    long long res=0;
    for(;pos;pos-=pos & -pos)
        res+=bit[pos];
    return res;
}

void Add(std::vector<long long> &bit,int pos,int v) {
    for(int n=bit.size();pos<n;pos+=pos & -pos)
        bit[pos]+=v;
}

struct Edge {
    int to,v;Edge *pre;

    Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre) {}
}*G[XN];

void Adde(int x,int y,int v) {
    G[x]=new Edge(y,v,G[x]);
    G[y]=new Edge(x,v,G[y]);
}

int circle[XN],circ;
bool ud[XN];
bool FindCircle(int pos,int pred) {
    static int stack[XN],top;
    if(ud[pos]) {
        circ=0;
        do {
            circle[++circ]=stack[top--];
        }while(stack[top+1]!=pos);
        top=0;
        return 1;
    } else {
        ud[stack[++top]=pos]=1;
        for(Edge *e=G[pos];e;e=e->pre) {
            int u=e->to;
            if(u!=pred && FindCircle(u,pos))
                return 1;
        }
        top--;
        return 0;
    }
}

int dc,lbd[XN],rbd[XN],par[XN][XLOGN],dep[XN],belong[XN];
std::vector<long long> bit[XN];
void DFS(int pos,int fa) {
    lbd[pos]=rbd[pos]=++dc;//rbd 0
    par[pos][0]=fa;
    for(int lg=1;lg<=lg2[dep[pos]];++lg)
        par[pos][lg]=par[par[pos][lg-1]][lg-1];
    for(Edge *e=G[pos];e;e=e->pre) {
        int u=e->to;
        if(u!=fa && !belong[u]) {
            belong[u]=belong[pos];
            dep[u]=dep[pos]+1;
            DFS(u,pos);
            rbd[pos]=rbd[u];
        }
    }
}

int LCA(int u,int v) {
    if(dep[u]<dep[v])
        std::swap(u,v);
    for(int lg=lg2[dep[u]-dep[v]];~lg;--lg)
        if((dep[u]-dep[v])>>lg&1)
            u=par[u][lg];
    if(u!=v) {
        for(int lg=lg2[dep[u]];~lg;--lg)
            if((1<<lg)<=dep[u] && par[u][lg]!=par[v][lg]) {//多出来的需要清0!! 可能走出(1<<(lg+1))-1步!
                u=par[u][lg];
                v=par[v][lg];
            }
        u=par[u][0];
    }
    return u;
}
void AddVal(int x,int y,int v) {
    if(circle[belong[x]]!=x || circle[belong[y]]!=y) {
        if(dep[x]>dep[y])
            std::swap(x,y);
        Add(bit[belong[x]],lbd[y],v);
        Add(bit[belong[x]],rbd[y]+1,-v);
    }  else {
        if(belong[x]>belong[y])
            std::swap(x,y);
        if(belong[x]+1==belong[y])
            Add(bit[0],belong[y],v);
        else
            Add(bit[0],belong[x],v);//belong[x]==1
    }
}

long long Query(int p1,int p2) {
    long long len1=Sum(bit[belong[p1]],lbd[p1]),len2=Sum(bit[belong[p2]],lbd[p2]);
    if(belong[p1]==belong[p2]) {
        long long lca=LCA(p1,p2),len3=Sum(bit[belong[lca]],lbd[lca]);
        return len1+len2-2*len3;
    } else {
        p1=belong[p1],p2=belong[p2];
        if(p1>p2) std::swap(p1,p2);
        long long len3=Sum(bit[0],p2)-Sum(bit[0],p1),len4=Sum(bit[0],circ)-len3;
        return len1+len2+std::min(len3,len4);
    }
}

void Work() {
    static struct Edges { int x,y,v; }edges[XN];
    int n,m;fin>>n>>m;
    for(int i=1;i<=n;++i) {
        G[i]=0;
        ud[i]=0;
        belong[i]=0;
    }
    for(int i=1;i<=n;++i) {
        fin>>edges[i].x>>edges[i].y>>edges[i].v;
        Adde(edges[i].x,edges[i].y,edges[i].v);
    }
    FindCircle(1,0);
    bit[0].resize(circ+1);
    std::fill(bit[0].begin(),bit[0].end(),0);
    for(int i=1;i<=circ;++i)
        belong[circle[i]]=i;
    for(int i=1;i<=circ;++i) {
        int pos=circle[i];
        dc=0;dep[pos]=0;
        DFS(pos,0);
        bit[i].resize(dc+1);
        std::fill(bit[i].begin(),bit[i].end(),0);
    }
    for(int i=1;i<=n;++i) {
        int x=edges[i].x,y=edges[i].y,v=edges[i].v;
        AddVal(x,y,v);
    }
    for(int i=1;i<=m;++i) {
        int op,x,y;fin>>op>>x>>y;
        if(op==1) {
            fout<<Query(x,y)<<'\n';
        } else {
            AddVal(edges[x].x,edges[x].y,-edges[x].v);
            AddVal(edges[x].x,edges[x].y,edges[x].v=y);
        }
    }
}
int main() {
    lg2[0]=-1;
    for(int i=1;i<XN;++i)
        lg2[i]=lg2[i>>1]+1;
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}