Luogu5236 静态仙人掌
传送门
题解
考虑可以把圆方树建出来,然后剩下只需要考虑两点之间的最短路.
-
如果两个点在圆方树上的(lca)是一个圆点,那么直接用树上差分即可.
-
如果两个点在圆方树上的(lca)是一个方点,此时等同于两个点的路径上有一堆点在同一个点双连通分量里面.
对于第二种,我们考虑对于一个环有两种走法,直接找到方点下面的圆点然后讨论即可.
JOJO我再也不写倍增了.
代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<iostream>
#include<set>
#include<map>
using namespace std;
#define mp make_pair
#define ll long long
#define re register
typedef pair<int,int> pii;
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
int f=1,sum=0;char ch=getchar();
while(ch>'9'&&ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=200010;
struct node{int to,nxt,w;}e[N<<2];
vector<pii>G[N];
int cnt,front[N],dep[N],dis[N],low[N],dfn[N],Time,fa[N],n,m,Q,S[N],tot,len[N],ri[N];
int f[N][22];
void add_edge(int u,int v,int w){e[++cnt]=(node){v,front[u],w};front[u]=cnt;}
void add(int u,int v,int w){G[u].push_back(mp(v,w));G[v].push_back(mp(u,w));}
void build(int u,int v,int w)
{
int sz=dep[v]-dep[u]+1,SUM=w,nd=0,ret=sz;
for(int i=v;i!=u;i=fa[i])S[ret--]=i,SUM+=dis[i]-dis[fa[i]];
S[1]=u;tot++;len[tot]=SUM;
for(int i=1;i<=sz;i++)
{
int d=min(nd,SUM-nd);
add(tot,S[i],d);ri[S[i]]=(d==nd);
nd+=dis[S[i+1]]-dis[S[i]];
}
}
void tarjan(int u,int ff)
{
dfn[u]=low[u]=++Time;dep[u]=dep[ff]+1;fa[u]=ff;
for(int i=front[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].w;if(v==ff)continue;
if(!dfn[v])
{
dis[v]=dis[u]+w;tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
if(dfn[u]<low[v])add(u,v,w);
}
for(int i=front[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].w;if(v==ff)continue;
if(fa[v]!=u&&dfn[u]<dfn[v])build(u,v,w);
}
}
int siz[N],son[N],top[N],b[N];
void dfs1(int u,int ff)
{
f[u][0]=fa[u]=ff;dep[u]=dep[ff]+1;siz[u]=1;
for(auto p:G[u])
{
int v=p.first,w=p.second;if(v==ff)continue;
dis[v]=dis[u]+w;dfs1(v,u);siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;dfn[u]=++Time;b[Time]=u;
if(!son[u])return;dfs2(son[u],tp);
for(auto p:G[u]){int v=p.first;if(v!=fa[u]&&v!=son[u])dfs2(v,v);}
}
int jump(int x,int y)
{
int s=0;
while(top[x]^top[y]){s=top[x];x=fa[s];}
return x==y?s:b[dfn[y]+1];
}
int getlca(int x,int y)
{
while(top[x]^top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}
return dep[x]<dep[y]?x:y;
}
int query(int u,int v)
{
int lca=getlca(u,v);
if(lca<=n)return dis[u]+dis[v]-2*dis[lca];
int pu=jump(u,lca),pv=jump(v,lca),d1=dis[pu]-dis[lca],d2=dis[pv]-dis[lca];
if(!ri[pu])d1=len[lca]-d1;if(!ri[pv])d2=len[lca]-d2;
return dis[u]-dis[pu]+dis[v]-dis[pv]+min(abs(d1-d2),len[lca]-abs(d1-d2));
}
int main()
{
tot=n=gi();m=gi();Q=gi();
for(int i=1;i<=m;i++)
{
int u=gi(),v=gi(),w=gi();
add_edge(u,v,w);add_edge(v,u,w);
}
tarjan(1,0);
memset(fa,0,sizeof(fa));memset(dep,0,sizeof(dep));memset(dis,0,sizeof(dis));
Time=0;dfs1(1,0);dfs2(1,1);
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
while(Q--)printf("%d
",query(gi(),gi()));
return 0;
}