【图论】 【树状数组】Traffic Network in Numazu

分析：

用LCT水过去当然也是可以的啦。。。。
不过这里讲一下不用LCT的方法。。（当然也不是树链剖分）

这个图肯定是一颗基环外向树，先忽略环，剩下的一定是一个森林。

对于每个森林，其实可以用dfn+树状数组维护没两点之间的距离：
按照dfn，在每个位置存储它到达当前根节点的距离，然后询问在同一颗树中的点时，可以用lca求出两点最近公共祖先，两点距离就是$dist(u)+dist(v)-2*dist(lca)$
每次修改边权时，显然会影响一颗子树，而在dfn中它们又是连续的。

所以可以使用树状数组的区间修改+单点查询（差分），就能在logn复杂度内支持询问，修改两个操作。

对于环上的，我们可以直接用树状数组的单点修改+区间查询。

然后如果询问不在同一颗子树内，那就直接先到环上，然后转化成求环上两点的距离。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 300010
using namespace std;
typedef long long ll;
vector<int> a[MAXN],cir;
ll tree[MAXN];
int n,q,bas[MAXN],root[MAXN],dfn[MAXN],cnt,lft[MAXN],sum[MAXN];
int dep[MAXN];
int fa[MAXN][20];
bool vis[MAXN];
void init(){
    cnt=0;
    cir.clear();
    for(int i=1;i<=n;i++){
        vis[i]=dfn[i]=lft[i]=sum[i]=0;
        a[i].clear();
        bas[i]=0;
        tree[i]=0;
        root[i]=0;
        dep[i]=0;
        fa[i][0]=0;
    }
}
struct Edge{
    int u,v,val;
    Edge () {}
    Edge (int u1,int v1,int val1):u(u1),v(v1),val(val1) {}  
}l[MAXN];
int dfs(int x,int f){
    vis[x]=1;
    for(int i=0;i<a[x].size();i++){
        int u=a[x][i];
        if(u==f)
            continue;
        if(vis[u]){
            cir.push_back(x);
            return u;
        }
        int res=dfs(u,x);
        if(res){
            cir.push_back(x);
            return res*(res!=x);
        }
    }
    return 0;
}
void dfs1(int x,int f,int base,int rt,int deep){
    if(dfn[x]==0){
        dfn[x]=++cnt;
        bas[x]=base;
        fa[x][0]=f;
        dep[x]=deep;
    }
    root[x]=rt;
    for(int i=0;i<a[x].size();i++){
        int u=a[x][i];
        if(dfn[u]||u==f)
            continue;
        dfs1(u,x,base,rt,deep+1);   
    }
    lft[x]=cnt;
}
int lca(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=19;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y)
        return x;
    for(int i=19;i>=0;i--)
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];
}
void Add(int x,int val,int base){
    while(x<=sum[base]){
        tree[x+base]+=val;
        x+=x&(-x);
    }
}
ll ask(int x,int base){
    ll res=0;
    while(x){
        res+=tree[x+base];
        x-=x&(-x);
    }
    return res;
}
void solve(int id,ll pre,ll val){
    int u=l[id].u,v=l[id].v;
    if(dfn[u]>dfn[v])
        swap(u,v);
    if(bas[v]==0){
        if(dfn[u]==1&&dfn[v]==sum[0]){
            //PF("[%d %lld}n",sum[0],val);
            Add(sum[0],val-pre,0);
        }
        else{
            //PF("[%d %lld]n",dfn[u],val);
            Add(dfn[u],val-pre,0);
        }
    }
    else{
        //PF("[%d %d %lld]n",dfn[v],lft[v]+1,val);
        Add(dfn[v]-bas[v],val-pre,bas[v]);
        Add(lft[v]+1-bas[v],pre-val,bas[v]);
    }
}

ll que(int u,int v){
    if(dfn[u]<dfn[v])
        swap(u,v);
    if(bas[u]!=bas[v]){
        ll ls=0,rs=0;
        if(bas[u])
            ls=ask(dfn[u]-bas[u],bas[u]);
        if(bas[v])
            rs=ask(dfn[v]-bas[v],bas[v]);
        //PF("{%lld %lld}n",ls,rs);
        return ls+rs+que(root[u],root[v]);
    }
    else{
        if(bas[u]==0){
            return min(ask(dfn[u]-1,0)-ask(dfn[v]-1,0),ask(sum[0],0)-ask(dfn[u]-1,0)+ask(dfn[v]-1,0));
        }
        else{
            int l=lca(u,v);
            if(bas[l]==0)
                return ask(dfn[u]-bas[u],bas[u])+ask(dfn[v]-bas[v],bas[v]);
            return ask(dfn[u]-bas[u],bas[u])+ask(dfn[v]-bas[v],bas[v])-2ll*ask(dfn[l]-bas[l],bas[l]);
        }
    }
}
int main(){
    //freopen("k.in","r",stdin);
    //freopen("wa.txt","w",stdout);
    int t,u,v,val,tag,id;
    SF("%d",&t);
    while(t--){
        SF("%d%d",&n,&q);   
        init();
        for(int i=1;i<=n;i++){
            SF("%d%d%d",&u,&v,&val);
            a[u].push_back(v);
            a[v].push_back(u);
            l[i]=Edge(u,v,val);
        }
        dfs(1,0);
        for(int i=0;i<cir.size();i++)
            dfn[cir[i]]=++cnt;
        sum[0]=cnt;
        for(int i=0;i<cir.size();i++){
            int cnt1=cnt;
            dfs1(cir[i],-1,cnt,cir[i],0);
            sum[cnt1]=cnt-cnt1;
        }
        /*for(int i=1;i<=n;i++){
            PF("{%d %d %d}n",i,bas[i],dfn[i]); 
        }*/
        for(int i=1;i<20;i++)
            for(int j=1;j<=n;j++)
                fa[j][i]=fa[fa[j][i-1]][i-1];
        for(int i=1;i<=n;i++)
            solve(i,0,l[i].val);
        for(int i=1;i<=q;i++){
            SF("%d",&tag);
            if(tag==0){
                SF("%d%d",&id,&val);
                solve(id,l[id].val,val);
                l[id].val=val;
            }
            else{
                SF("%d%d",&u,&v);
                PF("%I64dn",que(u,v));
            }
        }
    }
}

最后

以上就是感性鸡翅为你收集整理的【图论】 【树状数组】Traffic Network in Numazu的全部内容，希望文章能够帮你解决【图论】 【树状数组】Traffic Network in Numazu所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。