正题

题目链接:

题目大意

给一个边仙人掌（一条边至多在一个环中），每次询问两点之间的距离

解题思路

我们对于每个环新建方点，然后方点连向所有环上的点，然后计算一下每一条的边权

需要注意的是，如果两个询问点的 $L C A$ 是一个方点，那么需要特判

$c o d e$

#include
   
    #include
    
     #include
     
      using namespace std;const int N=3e4+10,K=18;struct node{
   	int to,next,w;}a[N*2],e[N*2];int n,m,q,tot,num,cnt;int f[N][K],s[N],val[N],dep[N],dis[N];int ls[N],rs[N],dfn[N],low[N];void addl(int x,int y,int w){
   	a[++tot].to=y;	a[tot].next=ls[x];	a[tot].w=w;	ls[x]=tot;}void adde(int x,int y,int w){
   	e[++tot].to=y;	e[tot].next=rs[x];	e[tot].w=w;	rs[x]=tot;}void circle(int x,int y,int w){
   	num++;int now=y,sum=w;	while(now!=f[x][0]){
   		s[now]=sum;		sum+=val[now];		now=f[now][0];	}	sum=s[num]=s[x];	s[x]=0;now=y;	int Dis;	while(now!=f[x][0]){
   		Dis=min(s[now],sum-s[now]);		adde(num,now,Dis);		adde(now,num,Dis);		now=f[now][0];	}	return;}void tarjan(int x){
   	dfn[x]=low[x]=++cnt;	int flag=0;	for(int i=ls[x];i;i=a[i].next){
   		int y=a[i].to;		if(y==f[x][0])continue;		if(!dfn[y]){
   			f[y][0]=x;			val[y]=a[i].w;tarjan(y);			low[x]=min(low[x],low[y]);		}		else low[x]=min(low[x],dfn[y]);		if(low[y]<=dfn[x])continue;		adde(x,y,a[i].w);adde(y,x,a[i].w);	}	for(int i=ls[x];i;i=a[i].next){
   		int y=a[i].to;		if(x==f[y][0]||dfn[x]>=dfn[y])continue;		circle(x,y,a[i].w);	}	return;}void dfs(int x,int fa){
   	for(int i=rs[x];i;i=e[i].next){
   		int y=e[i].to;		if(y==fa)continue;		dep[y]=dep[x]+1;		dis[y]=dis[x]+e[i].w;		f[y][0]=x;dfs(y,x);	}	return;}int Get_dis(int x,int y){
   	int u=x,v=y;	if(dep[x]>dep[y])swap(x,y);	for(int i=K-1;i>=0;i--)		if(dep[f[y][i]]>=dep[x])			y=f[y][i];	int lca;	if(x!=y){
   		for(int i=K-1;i>=0;i--)			if(f[x][i]!=f[y][i])				x=f[x][i],y=f[y][i];		lca=f[x][0];	}	else lca=x;	if(lca<=n)return dis[u]+dis[v]-dis[lca]*2;	else {
   		int ans=dis[u]-dis[x]+dis[v]-dis[y];		return ans+min(s[lca]-abs(s[x]-s[y]),abs(s[x]-s[y]));	}}int main(){
   	scanf("%d%d%d",&n,&m,&q);	num=n;	for(int i=1;i<=m;i++){
   		int x,y,w;		scanf("%d%d%d",&x,&y,&w);		addl(x,y,w);addl(y,x,w);	}	tot=0;tarjan(1);	dep[1]=1;dfs(1,0);	for(int i=1;i