专栏文章

题解：CF838B Diverging Directions

HHPXXZYY
CF838B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miptsb2c
此快照首次捕获于
2025/12/03 17:49
3 个月前
此快照最后确认于
2025/12/03 17:49
3 个月前
查看原文
[Problem Discription]\color{blue}{\texttt{[Problem Discription]}}
给定一个 nn 个点，(2n−2)(2n-2) 条边的有向图，每条边有边权。前 (n−1)(n-1) 条边构成一棵以 11 为根的树，边的方向远离根；后 (n−1)(n-1) 条边为每个点到 11 的边。每次操作修改其中一条边的边权，或求出从 uu 到 vv 的最短路。
边权为 [1,1×106][1,1 \times 10^{6}] 间的整数。
[Analysis]\color{blue}{\texttt{[Analysis]}}
从 uu 到 vv 的路径其实很少。
  1. 如果 uu 能沿着树上的边走到 vv，那肯定沿着树走最优。
  2. 否则 uu 必须先回到 11，再从 11 沿着树走到 vv。
维护 11 沿着树到每个点的距离（基为 Len(u)\text{Len}(u)），当修改一条树上边的时候，整棵子树内所有点的距离都将发生变化，但是变化量相同。利用树的深度优先遍历序（即 dfs\text{dfs} 序）连续的性质，可以用线段树维护这个距离。
然后第 11 种情况的答案其实就是 Len(v)−Len(u)\text{Len}(v)-\text{Len}(u)。
这里其实利用了差分的思想，将区间求和的问题转化为了前缀和相减。
考虑求出 uu 回到 11 的最短路。
从直觉上讲，很容易以为就是后 (n−1)(n-1) 条边的权值。但是显然 too young too simple 了。
uu 虽然不能沿着树的父亲回到 11，但它可以先到自己的某个子孙再回到 11。假设 uu 走到子树内的节点 ww 再从 ww 回到 11，那么路径的长度就是：
lu,w+valwl_{u,w}+\text{val}_w
其中 lu,wl_{u,w} 表示在树上从 uu 到 ww 的距离，valw\text{val}_{w} 表示 ww 到 11 的边的长度。
显然这样是求不出来的。但是 lu,w=Lenw−Lenul_{u,w}=\text{Len}_{w}-\text{Len}_{u}，于是上面式子改写成：
(Lenw+valw)−Lenu\left ( \text{Len}_{w} + \text{val}_{w} \right )-\text{Len}_{u}
括号内的项仅和 ww 有关，括号外仅和 uu 有关。可以用线段树维护括号内的项，这样就可以单次 O(log⁡n)O(\log n) 地求出所需结果。
这也是一个经典的 trick。如果一个式子里含有两个变量，那一般的数据结构都是无法维护的。分离变量是一个很好的方法。
具体实现看代码。
北航 XCPC 春季集训第二场比赛的 D 题。
考场上那些傻瓜错误：
  1. 把有向图看成无向图（但其实主体思路没有太大变化！）。
  2. 没有考虑到 uu 可以先走到子树再回根。
  3. 数组开太小了……
[Code]\color{blue}{\text{[Code]}}
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...