「CF838B」 Diverging Directions

题意

给出一个n个点2n-2条边的有向图。n-1条指向远离根方向的边形成一棵树，还有n-1条从非根节点指向根节点的边。

q次操作，1修改第x条边权值为y，2询问，求u到v的最短距离。

题解

在前n-1条边上dfs得到dfs序。

用线段树维护从根到区间里的点的最短距离，和从根到区间里的点再回去的最短距离。

修改第一条边的边权时，就修改了根到这条边指向的点为根的子树里每个点的距离。x为根的子树的点dfs序为L[x]~R[x]。

修改第二种边的边权时，只影响根到这条边出发点再回去的最短距离。

查询时，如果u是v的祖先，最短距离就是根到v的距离减去根到u的距离;不是祖先时，那就是从u为根的子树里的点回到根的最短距离加上根到v的距离。

代码

#include <bits/stdc++.h>

#define N 1<<18

#define ll long long

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

struct SegTree{

	int n;

	ll tree[N<<2],lazy[N<<2];

	void init(int _n){

		n=_n;

		mem(tree,0);

		mem(lazy,0);

	}

	void pushdown(int node){

		lazy[node<<1]+=lazy[node];

		tree[node<<1]+=lazy[node];

		lazy[node<<1|1]+=lazy[node];

		tree[node<<1|1]+=lazy[node];

		lazy[node]=0;

	}

	void update(int node,int l,int r,int L,int R,ll value){

		if(L>R || l>R || r<L) return;

		if(L<=l && r<=R){

			tree[node]+=value;

			lazy[node]+=value;

			return;

		}

		pushdown(node);

		update(node<<1,l,l+r>>1,L,R,value);

		update(node<<1|1,(l+r>>1)+1,r,L,R,value);

		tree[node]=min(tree[node<<1],tree[node<<1|1]);

	}

	ll query(int node,int l,int r,int L,int R){

		if(L>R || l>R || r<L) return numeric_limits < ll > ::max();

		if(L<=l && r<=R){

			return tree[node];

		}

		pushdown(node);

		return min(query(node<<1,l,l+r>>1,L,R),

				query(node<<1|1,(l+r>>1)+1,r,L,R));

	}

	void update(int L,int R,ll value){

		update(1,1,n,L,R,value);

	}

	ll query(int L,int R){

		return query(1,1,n,L,R);

	}

}from_root,from_root_and_back;

struct Edge{

	int to,next,w;

}e[N];

int head[N],cnt;

void add(int u,int v,int w){

	e[++cnt]=(Edge){v,head[u],w};

	head[u]=cnt;

}

int from[N<<1];

int L[N],R[N],idx;

ll dis[N];

void dfs(int x,int fa){

	L[x]=R[x]=++idx;

	for(int i=head[x];i;i=e[i].next){

		int v=e[i].to;

		if(v!=fa){

			dis[v]=dis[x]+e[i].w;

			dfs(v,x);

			R[x]=R[v];

		}

	}

}

ll dep(int x){

	return from_root.query(L[x],L[x]);

}

ll back[N];

int main(){

	int n,q;

	scanf("%d%d", &n, &q);

	int u,v,w;

	for(int i=1;i<n;++i){

		scanf("%d%d%d", &u, &v, &w);

		add(u,v,w);

		from[i]=u;

	}

	for(int i=1;i<n;++i){

		scanf("%d%d%d", &u, &v, &w);

		back[u]=w;

		from[i+n-1]=u;

	}

	from_root.init(n);

	from_root_and_back.init(n);

	dfs(1,0);

	for(int i=1;i<=n;++i){

		from_root.update(L[i],L[i],dis[i]);

		from_root_and_back.update(L[i],L[i],dis[i]+back[i]);

	}

	while(q--) {

		int o,x,y;

		scanf("%d%d%d", &o, &x, &y);

		if(o&1) {

			if(x<n) {

				int v=e[x].to,u=from[x],d=y-dep(v)+dep(u);

				from_root.update(L[v],R[v],d);

				from_root_and_back.update(L[v],R[v],d);

			}

			else {

				int u=from[x],d=y-back[u];back[u]=y;

				from_root_and_back.update(L[u],L[u],d);

			}

		}

		else {

			if(L[x]<=L[y]&&R[y]<=R[x])

				printf("%lld\n", dep(y)-dep(x));

			else

				printf("%lld\n",from_root_and_back.query(L[x],R[x])-dep(x)+dep(y));

		}

	}

	return 0;

}

巴特西

「CF838B」 Diverging Directions

题意

题解

代码

最新文章

热门文章