题面

思路

考场想到 \(tarjan\) 缩点

然而忘了缩点怎么打

于是甩了个暴力

改题时学了个圆方树

发现挺好用

于是······注意重边

\(Code\)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<map>
using namespace std;

const int N = 3e5 + 5;
int n , m , q , cnt , tot1 , tot2 , top , dfc;
int p[N][2] , h1[N] , h2[N] , dfn[N] , low[N] , df[N] , f[N][22] , fa[N][22] , dep[N];
map<pair<int , int> , int> mp;

struct edge1{
    int nxt , to , w;
}e1[N * 2];
struct edge2{
    int nxt , to , w;
}e2[N * 2];
struct node{
    int x , z;
}stack[N];

void add1(int x , int y , int z)
{
    e1[++tot1] = edge1{h1[x] , y , z};
    h1[x] = tot1;
}
void add2(int x , int y , int z)
{
    e2[++tot2] = edge2{h2[x] , y , z};
    h2[x] = tot2;
}

void tarjan(int x , int fa , int z)
{
    stack[++top] = node{x , z};
    low[x] = dfn[x] = ++dfc;
    for(register int i = h1[x]; i; i = e1[i].nxt)
    {
        int v = e1[i].to;
        if (!dfn[v])
        {
            tarjan(v , x , e1[i].w) , low[x] = min(low[x] , low[v]);
            if (dfn[x] < low[v]) add2(x , v , e1[i].w) , df[v] = e1[i].w , --top;
            else if (dfn[x] == low[v])
            {
                int BBC = 0 , tp = top;
                for(register int j = h1[x]; j; j = e1[j].nxt)
                if (e1[j].to == stack[top].x){BBC = e1[j].w; break;}
                add2(x , ++cnt , 0);
                while (stack[tp].x != x) df[stack[tp].x] = BBC , BBC += stack[tp].z , --tp;
                while (stack[top].x != x)
                    add2(cnt , stack[top].x , min(df[stack[top].x] , BBC - df[stack[top].x])) , --top;
                df[cnt] = BBC;
            }
        }
        else if (v != fa) low[x] = min(low[x] , dfn[v]);
    }
}

void dfs(int x , int d)
{
    dep[x] = d;
    for(register int i = 1; i <= 20; i++)
    if (fa[x][i - 1]) fa[x][i] = fa[fa[x][i - 1]][i - 1] , f[x][i] = f[x][i - 1] + f[fa[x][i - 1]][i - 1];
    else break;
    for(register int i = h2[x]; i; i = e2[i].nxt)
    {
        fa[e2[i].to][0] = x , f[e2[i].to][0] = e2[i].w;
        dfs(e2[i].to , d + 1);
    }
}

int getans(int x , int y)
{
    int u = x , v = y;
    if (dep[u] < dep[v]) swap(u , v);
    int deep = dep[u] - dep[v] , res = 0;
    for(register int i = 0; i <= 20; i++)
    if (deep & (1 << i)) res += f[u][i] , u = fa[u][i];
    if (u == v) return res;
    for(register int i = 20; i >= 0; i--)
    if (fa[u][i] != fa[v][i]) res += f[u][i] + f[v][i] , u = fa[u][i] , v = fa[v][i];
    if (fa[u][0] <= n) return res + f[u][0] + f[v][0];
    return res + min(abs(df[u] - df[v]) , df[fa[u][0]] - abs(df[u] - df[v]));
}

int main()
{
    freopen("garden.in" , "r" , stdin);
    freopen("garden.out" , "w" , stdout);
    scanf("%d%d" , &n , &m);
    int x , y , z;
    for(register int i = 1; i <= m; i++)
    {
        scanf("%d%d%d" , &x , &y , &z);
        if (x > y) swap(x , y);
        p[i][0] = x , p[i][1] = y;
        if (mp[make_pair(x , y)] == 0) mp[make_pair(x , y)] = z;
        else mp[make_pair(x , y)] = min(mp[make_pair(x , y)] , z);
    }
    for(register int i = 1; i <= m; i++)
    {
        x = p[i][0] , y = p[i][1] , z = mp[make_pair(x , y)];
        add1(x , y , z) , add1(y , x , z);
    }
    cnt = n;
    tarjan(1 , 0 , 0);
    dfs(1 , 0);
    scanf("%d" , &q);
    for(register int i = 1; i <= q; i++)
    {
        scanf("%d%d" , &x , &y);
        printf("%d\n" , getans(x , y));
    }
}