HDU - 6393 Traffic Network in Numazu(线段树+LCA+树链剖分+并查集)

86 阅读 0 评论 57 点赞

我是靠谱客的博主无私百合，最近开发中收集的这篇文章主要介绍HDU - 6393 Traffic Network in Numazu(线段树+LCA+树链剖分+并查集)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击查看

题目大意：给出一个由n个点和n条边组成的图，每条边都有权值，题目保证图是连通的，然后给出m个询问，每次询问分为两种形式：

0 x y：将第x条边的权值修改为y
1 x y：查询x-y这条路径上的权值和

题目分析：因为这个题目故意给的是n个点和n条边，所以我们可以发现这一定是一个有环的图，如果n个点和n-1条边组成一棵树的话会多出一条边来，那么先让他多出来不要管，至于怎么求这个多出来的边，我们直接用并查集操作一下就行了，因为上面也提到了，多出来一条边肯定会组成环，所以多出来的那条边会发现早就已经加入到集合中去了，单独拿出来就行

针对这两个操作我们需要分析一下，如果没有第一个操作的话，那就是一个简单的树上求前缀和的问题了，我们只需要特判一下多出来的那条边即可，大体思路就是先用树上倍增或树链剖分跑一下lca，然后用树上前缀和求一下u-lca(u,v)-v这条路径上的权值和，但是我们该怎么特判多出来的那条边呢？

假如让我们求的是x到y这条路径上的权值和，而多出来的那条边的两个顶点是u和v，权值为w，那么我们可以先跑一下下面三个值，求一下最小值就是答案了：（sum[i]代表根节点到i节点的前缀和）

sum[x]+sum[y]-2*sum[lca(x,y)]//不经过多出来的那条边：x-lca(x,y)-y
(sum[x]+sum[v]-2*sum[lca(x,v)])+(sum[y]+sum[u]-2*sum[lca(y,u)])+w//经过多出来的那条边：x-lca(x,v)-v-u-lca(u,y)-y
(sum[x]+sum[u]-2*sum[lca(x,u)])+(sum[y]+sum[v]-2*sum[lca(y,v)])+w//经过多出来的那条边：x-lca(x,u)-u-v-lca(v,y)-y

但是！这个题目是需要修改的，在树上看到修改无非就是往线段树和树状数组上靠拢了，因为我对树状数组的理解不太够，所以还是选择比较好用的线段树来维护吧，具体就是先用树链剖分将整个树剖一下，然后因为边权比较难处理，就将边权映射到点权上，昨天刚做了一个类似的题目，于是就很好处理了，记着特别处理一下最后到根节点那条链上的关系就好，再一一对应到线段树上，就可以写一个getnum函数用来以logn*logn的时间复杂度获取任意一点到根节点的权值和了，也就是上面提到的前缀和，然后对于修改操作的话，如果是多出来的那条边，我们直接修改就行，如果是树上的边，用线段树logn修改一下就好了，这个题我感觉比较讨厌的地方是关于两端映射，有两个地方需要用到映射，一个是树剖打dfs序的时候需要将序号和节点映射一下，还有就是关于每一条边和映射到的节点也需要对应好，注意好这些细节，写代码尽量多用函数包装一下，这样写完后debug起来也比较轻松

废话不多说了，最后就是记得所有与权值相关的地方都开一下longlong，因为1e5*1e5就爆掉int了

代码：

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e5+100;

int n,m;

struct Edge
{
	int u,v,id;
	LL w;
	Edge(int U,int V,LL W,int ID)
	{
		u=U;
		v=V;
		w=W;
		id=ID;
	}
	Edge(){}
}edge[N];//存边用

vector<Edge>node[N];//邻接表

struct Node
{
	int l,r;
	LL sum;
}tree[N<<2];//线段树用

int rk[N];//边权与点权的映射 rk[编号]=节点

LL val[N];//边权与点权的映射 val[节点]=权值

int id[N],idd[N];//dfs序与节点的映射 id[节点]=dfs序 idd[dfs序]=节点

void pushup(int k)//以下为简单线段树维护sum和
{
	tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}

void build(int k,int l,int r)
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		tree[k].sum=val[idd[l]];
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}

void update(int k,int pos,int val)
{
	if(tree[k].l==tree[k].r)
	{
		tree[k].sum=val;
		return;
	}
	int mid=tree[k].l+tree[k].r>>1;
	if(mid>=pos)
		update(k<<1,pos,val);
	else
		update(k<<1|1,pos,val);
	pushup(k); 
}

LL query(int k,int l,int r)
{
	if(tree[k].r<l||tree[k].l>r)
		return 0;
	if(tree[k].l>=l&&tree[k].r<=r)
		return tree[k].sum;
	return query(k<<1,l,r)+query(k<<1|1,l,r);
}

int son[N],num[N],deep[N],fa[N];//树链剖分用

void dfs1(int u,int f,int dep)
{
	fa[u]=f;
	son[u]=-1;
	num[u]=1;
	deep[u]=dep;
	for(int i=0;i<node[u].size();i++)
	{
		int v=node[u][i].v;
		int w=node[u][i].w;
		int id=node[u][i].id;
		if(v==f)
			continue;
		val[v]=w;//将边权映射到点权上 
		rk[id]=v;
		dfs1(v,u,dep+1);
		num[u]+=num[v];
		if(son[u]==-1||num[son[u]]<num[v])
			son[u]=v;
	}
}

int top[N],tot;//树链剖分用

void dfs2(int u,int f,int root)
{
	top[u]=root;
	id[u]=++tot;
	idd[tot]=u;
	if(son[u]!=-1)
		dfs2(son[u],u,root);
	for(int i=0;i<node[u].size();i++)
	{
		int v=node[u][i].v;
		if(v==f||v==son[u])
			continue;
		dfs2(v,u,v);
	}
}

LL getnum(int x)//获得点1-点x的权值和 
{
	LL ans=0;
	while(top[x]!=1)
	{
		ans+=query(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(x==1)
		return ans;
	ans+=query(1,2,id[x]);//注意这里，虽然这给题目从1开始和从2开始没什么区别
	return ans;
}

int LCA(int a,int b)//树链剖分求lca
{
	while(top[a]!=top[b])
	{
		if(deep[top[a]]<deep[top[b]])
			swap(a,b);
		a=fa[top[a]];
	}
	if(a==b)
		return a;
	return deep[a]<deep[b]?a:b;
}

int f[N];//并查集用 

int find(int x)//并查集
{
	return x==f[x]?x:f[x]=find(f[x]);
}

void init()//初始化
{
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
		node[i].clear();
	}
	tot=0;
}

int main()
{
//  freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int w;
	cin>>w;
	while(w--)//按照上文中一步步实现即可
	{
		scanf("%d%d",&n,&m);
		init();
		int mark;
		for(int i=1;i<=n;i++)
		{
			int u,v;
			LL w;
			scanf("%d%d%lld",&u,&v,&w);
			edge[i].u=u;
			edge[i].v=v;
			edge[i].w=w;
			edge[i].id=i;
			int uu=find(u);
			int vv=find(v);
			if(uu!=vv)
			{
				f[uu]=vv;
				node[u].push_back(Edge(u,v,w,i));
				node[v].push_back(Edge(v,u,w,i));
			}
			else
				mark=i;
		}
		dfs1(1,0,0);
		dfs2(1,0,1);
		build(1,1,n);
		while(m--)
		{
			int op,x,y;
			scanf("%d%d%d",&op,&x,&y);
			if(op==0)
			{
				if(x==mark)
					edge[mark].w=y;
				else
					update(1,id[rk[x]],y);
			}
			else
			{
				int lca=LCA(x,y);
				LL ans=getnum(x)+getnum(y)-2*getnum(lca);
				int u=edge[mark].u;
				int v=edge[mark].v;
				int w=edge[mark].w;
				LL ans1=getnum(x)+getnum(u)-2*getnum(LCA(x,u))+getnum(y)+getnum(v)-2*getnum(LCA(y,v));
				LL ans2=getnum(x)+getnum(v)-2*getnum(LCA(x,v))+getnum(y)+getnum(u)-2*getnum(LCA(y,u));
				printf("%lldn",min(ans,min(ans1+w,ans2+w)));
			}
		}
	}
	
	
	
	
	
	
     
     
     
     
      
     
    return 0;
}