题解：CF838B Diverging Directions

· · 题解

\color{blue}{\texttt{[Problem Discription]}}

给定一个 n 个点，(2n-2) 条边的有向图，每条边有边权。前 (n-1) 条边构成一棵以 1 为根的树，边的方向远离根；后 (n-1) 条边为每个点到 1 的边。每次操作修改其中一条边的边权，或求出从 u 到 v 的最短路。

边权为 [1,1 \times 10^{6}] 间的整数。

\color{blue}{\texttt{[Analysis]}}

从 u 到 v 的路径其实很少。

  1. 如果 u 能沿着树上的边走到 v，那肯定沿着树走最优。
  2. 否则 u 必须先回到 1，再从 1 沿着树走到 v。

维护 1 沿着树到每个点的距离（基为 \text{Len}(u)），当修改一条树上边的时候，整棵子树内所有点的距离都将发生变化，但是变化量相同。利用树的深度优先遍历序（即 \text{dfs} 序）连续的性质，可以用线段树维护这个距离。

然后第 1 种情况的答案其实就是 \text{Len}(v)-\text{Len}(u)。

这里其实利用了差分的思想，将区间求和的问题转化为了前缀和相减。

考虑求出 u 回到 1 的最短路。

从直觉上讲，很容易以为就是后 (n-1) 条边的权值。但是显然 too young too simple 了。

$$l_{u,w}+\text{val}_w$$ 其中 $l_{u,w}$ 表示在树上从 $u$ 到 $w$ 的距离，$\text{val}_{w}$ 表示 $w$ 到 $1$ 的边的长度。 显然这样是求不出来的。但是 $l_{u,w}=\text{Len}_{w}-\text{Len}_{u}$，于是上面式子改写成： $$\left ( \text{Len}_{w} + \text{val}_{w} \right )-\text{Len}_{u}$$ 括号内的项仅和 $w$ 有关，括号外仅和 $u$ 有关。可以用线段树维护括号内的项，这样就可以单次 $O(\log n)$ 地求出所需结果。 > 这也是一个经典的 trick。如果一个式子里含有两个变量，那一般的数据结构都是无法维护的。分离变量是一个很好的方法。 具体实现看代码。 > 北航 XCPC 春季集训第二场比赛的 D 题。 > > **考场上那些傻瓜错误：** > 1. 把**有向图**看成无向图（但其实主体思路没有太大变化！）。 > 2. 没有考虑到 $u$ 可以先走到子树再回根。 > 3. 数组开太小了…… $\color{blue}{\text{[Code]}} 
int Fa[22][N],n,dep[N],q;
int u[N<<1],v[N<<1],w[N<<1],len[N];
int End[N],rec[N],dfscnt,Trans[N];
ll Len[N];
//len[i] 表示从 i 到 1 的直接边的长度 
//Len[i] 表示初始时 1 沿着树到 i 的总长度 

struct Segment_Tree{
    int ls[N<<1],rs[N<<1],rt,ndcnt;
    ll sum[N<<1],tag[N<<1],minn[N<<1];

    void pushup(int o){
        sum[o]=sum[ls[o]]+sum[rs[o]];
        minn[o]=min(minn[ls[o]],minn[rs[o]]);
    }
    void pushdown(int o,int l,int r){
        tag[ls[o]]+=tag[o];
        tag[rs[o]]+=tag[o];
        minn[ls[o]]+=tag[o];
        minn[rs[o]]+=tag[o];

        int mid=(l+r)>>1;
        sum[ls[o]]+=tag[o]*(mid-l+1);
        sum[rs[o]]+=tag[o]*(r-mid);

        tag[o]=0;
    }

    void build(int &o,int l,int r,int tpe){
        o=++ndcnt;
        tag[o]=sum[o]=minn[o]=0;

        if (l==r){
            if (tpe==1) sum[o]=minn[o]=Len[Trans[l]];
            else sum[o]=minn[o]=Len[Trans[l]]+len[Trans[r]];
            return;
        }

        int mid=(l+r)>>1;
        build(ls[o],l,mid,tpe);
        build(rs[o],mid+1,r,tpe);

        return pushup(o);
    }

    void modify(int o,int l,int r,int p,int q,int v){
        if (p<=l&&r<=q){
            tag[o]+=v;
            minn[o]+=v;
            sum[o]+=1ll*v*(r-l+1);
            return;
        }

        if (tag[o]) pushdown(o,l,r);

        int mid=(l+r)>>1;
        if (p<=mid) modify(ls[o],l,mid,p,q,v);
        if (mid<q) modify(rs[o],mid+1,r,p,q,v);

        return pushup(o);
    }
    ll query(int o,int l,int r,int p){
        if (l==r) return sum[o];
        if (tag[o]) pushdown(o,l,r);

        int mid=(l+r)>>1;
        if (p<=mid) return query(ls[o],l,mid,p);
        else return query(rs[o],mid+1,r,p);
    }
    ll query(int o,int l,int r,int p,int q){
        if (p<=l&&r<=q) return minn[o];
        if (tag[o]) pushdown(o,l,r);

        int mid=(l+r)>>1;ll ans=1e18;
        if (p<=mid) ans=min(ans,query(ls[o],l,mid,p,q));
        if (mid<q) ans=min(ans,query(rs[o],mid+1,r,p,q));

        return ans;
    }
}SGT,sgt;

struct edge{
    int nxt,to,len;
}e[N<<1];int h[N],ecnt;
void add(int u,int v,int w){
    e[++ecnt]=(edge){h[u],v,w};h[u]=ecnt;
}

void dfs(int u,int fa){
    rec[u]=++dfscnt;
    Trans[dfscnt]=u;

    dep[u]=dep[fa]+1;
    Fa[0][u]=fa;

    for(int i=1;i<=20;i++)
        Fa[i][u]=Fa[i-1][Fa[i-1][u]];

    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;
        if (v==fa) continue;

        Len[v]=Len[u]+e[i].len;
        dfs(v,u);
    }

    End[u]=dfscnt;//记录 dfs 序 
}
int LCA(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);

    for(int i=20;i>=0;i--)
        if (dep[Fa[i][u]]>=dep[v])
            u=Fa[i][u];

    if (u==v) return u;

    for(int i=20;i>=0;i--)
        if (Fa[i][u]!=Fa[i][v]){
            u=Fa[i][u];
            v=Fa[i][v];
        }

    return Fa[0][v];
}

ll query(int u){
    return sgt.query(sgt.rt,1,n,rec[u],End[u])-SGT.query(SGT.rt,1,n,rec[u]);
}
ll query(int u,int v){
    ll res;
    if (u==v) return 0;

    if (LCA(u,v)==u) res=SGT.query(SGT.rt,1,n,rec[v])-SGT.query(SGT.rt,1,n,rec[u]);
    else res=query(u)+SGT.query(SGT.rt,1,n,rec[v]);

    return res;
}

int main(int argv,char *argc[]){
    n=read();q=read();
    for(int i=1;i<n;i++){
        u[i]=read();
        v[i]=read();
        w[i]=read();

        add(u[i],v[i],w[i]);
        add(v[i],u[i],w[i]);
    }

    for(int j=1;j<n;j++){
        int i=j+(n-1);//真实边标号 

        u[i]=read();
        v[i]=read();//v[i] == 1
        w[i]=read();

        len[u[i]]=w[i];
    }

    dfs(1,0);
    SGT.build(SGT.rt,1,n,1);
    sgt.build(sgt.rt,1,n,2);

    for(int i=1;i<=q;i++){
        int opt=read(),s=read(),t=read();

        if (opt==1){
            if (s<n){//修改树上的边 
                SGT.modify(SGT.rt,1,n,rec[v[s]],End[v[s]],t-w[s]);
                sgt.modify(sgt.rt,1,n,rec[v[s]],End[v[s]],t-w[s]);
                //v[s] 的子树内所有点到 1 的距离发生变化 

                w[s]=t;
            }
            else{
                sgt.modify(sgt.rt,1,n,rec[u[s]],rec[u[s]],t-len[u[s]]);
                len[u[s]]=t;
            }
        }
        else printf("%lld\n",query(s,t));
    }

    return 0;
}