scy代码（暴力求LCA 超时，75分）：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
vector<pair<int,int>>G1[N],G2[N<<1];

int tsp,cnt,dfn[N],low[N];
stack<int>stk;
int rng[N<<1],w[N],tw[N];

void tarjan(int x)
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);
    for(auto i:G1[x])
    {
        int y=i.first,c=i.second;
        if(!dfn[y])
        {
            w[y]=w[x]+c;
            tarjan(y);
            low[x]=min(low[x],low[y]);
			if(dfn[x]==low[y])
            {
            	++cnt;//新增方点的编号
            	G2[x].push_back({cnt,0});
				rng[cnt]=w[stk.top()]-w[x] +  tw[stk.top()];//新增方点所代表的环的周长
            	for(int z=-1;z!=y;)
				{
					z=stk.top();stk.pop();
					G2[cnt].push_back({z,min(w[z]-w[x],rng[cnt]-(w[z]-w[x]))});
				}
				
            }  
        }
        else if(low[x]>dfn[y]) tw[x]=c,low[x]=dfn[y];
    }
}
int n,dep[N<<1],d[N<<1],up[N<<1];
void dfs(int x)
{
    for(auto i:G2[x])
    {
        int y=i.first,c=i.second;
        d[y]=d[x]+c;
        dep[y]=dep[x]+1;
        up[y]=x;
        dfs(y);
    }
}
int dist(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    int A=x,B=y;
    while(dep[x]>dep[y]) x=up[x];
    if(x==y) return d[A]-d[ B ];
    while(up[x]!=up[y])x=up[x],y=up[y];
    int lca=up[x];//或者 lca=up[y]
    if(lca<=n) return d[A]+d[ B ]-2*d[lca];
    else       return d[A]+d[ B ]-d[x]-d[y]
	                  +min( abs(w[x]-w[y]) , rng[lca]-abs(w[x]-w[y]) );
}
int main()
{
    int m,q;scanf("%d%d%d",&n,&m,&q);
    for(int i=1,x,y,c;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        G1[x].push_back({y,c});
        G1[y].push_back({x,c});
    }
    tsp=0;cnt=n;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    tarjan(1),stk.pop();//洁癖，最后1还在栈中
    memset(dep,0,sizeof(dep));memset(d,0,sizeof(d));memset(up,0,sizeof(up));
	dfs(1);
    while(q--)
    {
        int x,y;scanf("%d%d",&x,&y);
        printf("%d\n",dist(x,y));
    }
    return 0;
}

scy代码（标程：st表求LCA 100分）：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
vector<pair<int,int>>G1[N],G2[N<<1];
int tsp,cnt,dfn[N],low[N];
stack<int>stk;
int rng[N<<1],w[N],tw[N];

void tarjan(int x)
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);
    for(auto i:G1[x])
    {
        int y=i.first,c=i.second;
        if(!dfn[y])
        {
            w[y]=w[x]+c;
            tarjan(y);
            low[x]=min(low[x],low[y]);
			if(dfn[x]==low[y])
            {
            	++cnt;
				G2[x].push_back({cnt,0});
				rng[cnt]=w[stk.top()]-w[x] +  tw[stk.top()];
            	for(int z=-1;z!=y;)
				{
					z=stk.top();stk.pop();
					G2[cnt].push_back({z,min(w[z]-w[x],rng[cnt]-(w[z]-w[x]))});
				}
				
            }  
        }
        else if(low[x]>dfn[y]) tw[x]=c,low[x]=dfn[y];
    }
}
int n,D,dep[N<<1],d[N<<1],st[N<<1][20];
void dfs(int x)
{
    for(auto i:G2[x])
    {
        int y=i.first,c=i.second;
        d[y]=d[x]+c;
		dep[y]=dep[x]+1;
		st[y][0]=x;for(int i=1;i<=D;i++)st[y][i]=st[st[y][i-1]][i-1];
        dfs(y);
    }
}
int dist(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    int A=x,B=y;
    for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y]) x=st[x][i];
    if(x==y) return d[A]-d[ B ];
    for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
    int lca=st[x][0];

    if(lca<=n) return d[A]+d[ B ]-2*d[lca];
    else       return d[A]+d[ B ]-d[x]-d[y]
	                  +min( abs(w[x]-w[y]) , rng[lca]-abs(w[x]-w[y]) );
}
int main()
{
    int m,q;scanf("%d%d%d",&n,&m,&q);
    for(int i=1,x,y,c;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        G1[x].push_back({y,c});
        G1[y].push_back({x,c});
    }
    tsp=0;cnt=n;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    tarjan(1),stk.pop();
    D=log2(cnt);memset(dep,0,sizeof(dep));memset(d,0,sizeof(d));memset(st,0,sizeof(st));
	dfs(1);
    while(q--)
    {
        int x,y;scanf("%d%d",&x,&y);
        printf("%d\n",dist(x,y));
    }
    return 0;
}

D31 圆方树 P5236【模板】静态仙人掌(这个视频不推荐)
视频中的代码（同样不推荐）：

// Tarjan+倍增 O((n+m)logn)
#include<bits/stdc++.h>
using namespace std;

const int N=20000,M=N*3;
int n,m,Q;
struct edge{int v,w,ne;}e[M];
int h1[N],h2[N],idx=1;//建图
int dfn[N],low[N],tim;//tarjan
int s[N],sc[N],fa[N],fw[N],fe[N],cn;
int f[N][14],dep[N],d[N];//lca
int A,B;//存lca的两个儿子

void add(int h[],int a,int b,int c){
  e[++idx]={b,c,h[a]};h[a]=idx;
}
void build_tree(int u,int v,int w){
  int sum=w;
  for(int k=v;k!=u;k=fa[k]){
    s[k]=sum; //u...k的环长
    sum+=fw[k]; //前缀和
  }
  // s[u]=sc[u]=sum;
  add(h2,u,++cn,0);
  for(int k=v;k!=u;k=fa[k]){
    sc[k]=sum; //总环长
    add(h2,cn,k,min(s[k],sum-s[k]));
  }
}
void tarjan(int u,int ine){
  dfn[u]=low[u]=++tim;
  for(int i=h1[u];i;i=e[i].ne){
    int v=e[i].v,w=e[i].w;
    if(!dfn[v]){ //若没有访问
      //fw:存边权，fe:存入边
      fa[v]=u,fw[v]=w,fe[v]=i;
      tarjan(v,i);
      low[u]=min(low[u],low[v]);
      if(dfn[u]<low[v]) //非环边
        add(h2,u,v,w);//直接加边
    }
    else if(i!=(ine^1)) //构成环
      low[u]=min(low[u],dfn[v]);
  }
  for(int i=h1[u];i;i=e[i].ne){
    int v=e[i].v,w=e[i].w;
    if(dfn[u]<dfn[v]&&fe[v]!=i)
      build_tree(u,v,w); //建树
  }
}
void dfs(int u,int father){
  dep[u]=dep[father]+1;
  f[u][0]=father;
  for(int k=1;k<=13;k++)
    f[u][k]=f[f[u][k-1]][k-1];
  for(int i=h2[u];i;i=e[i].ne){
    int v=e[i].v,w=e[i].w;
    d[v]=d[u]+w;
    dfs(v,u);
  }
}
int lca(int u,int v){
  if(dep[u]<dep[v]) swap(u,v);
  for(int k=13;k>=0;k--)
    if(dep[f[u][k]]>=dep[v])
      u=f[u][k];
  if(u==v) return u;
  for(int k=13;k>=0;k--)
    if(f[u][k]!=f[v][k]){
      u=f[u][k];
      v=f[v][k];
    }
  A=u,B=v;//存lca的两个儿子
  return f[u][0];
}
int main(){
  scanf("%d%d%d",&n,&m,&Q);
  cn=n;
  while(m--){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);
    add(h1,a,b,c),add(h1,b,a,c);
  }
  tarjan(1,-1);//找环建树
  dfs(1,0);//lca打表
  while(Q--){
    int u,v;
    scanf("%d%d",&u,&v);
    int p=lca(u,v);//找lca
    if(p<=n) //若是圆点
      printf("%d\n",d[u]+d[v]-d[p]*2);
    else{ //若是方点
      int len=abs(s[A]-s[B]);
      int dAB=min(len,sc[A]-len);
      int dis=dAB+d[u]-d[A]+d[v]-d[B];
      printf("%d\n",dis);
    }
  }
}