1. 题目

传送门=￣ω￣=

大意：给你一个仙人掌，问你两点之间最短距离

2. 题解

其实这是第二遍做这题啦！

昨天生病了，QvQ，现在精神不佳，还是，，，水一下吧。

蒟蒻 XZY 决定更改代码风格，所以在这里存一下。

具体做法就是圆方树上 LCA。若 LCA 是圆点则两点之间距离可以直接视为树上距离。若 LCA 是方点则将两点之间距离视为 LCA 所在的环上的两个圆点的距离加上它们到所求两点的距离。

详见：

• KB：【算法】如何以正确的姿势种植一棵仙人掌
• immortalCO：圆方树——处理仙人掌的利器

代码（其实我主要还是来存代码的）：

#include <bits/stdc++.h>

#define NS (20005)
#define LGS (15)

using namespace std;

typedef long long LL;

template <typename _Tp>inline void IN (_Tp& dig)
{
    char c; bool flag=0; dig=0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0',c = getchar();
    if (flag) dig = -dig;
}

struct graph
{
    int head[NS], nxt[NS << 1], to[NS << 1], w[NS << 1], sz;
    void init () {memset(head, -1, sizeof(head)), sz=0;}
    graph () {init();}
    void push (int a, int b, int c)
    {
        nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
    }
}g, t;

int n, m, q, vis[NS], T, cir[NS], pre[NS], pdis[NS], dis[NS], squ;
int Pre[NS][LGS+1], dep[NS];
LL sum[NS], Deep[NS];

void bookc (int root, int bott)
{
    cir[root] = bott;
    while (bott != root) cir[bott] = -1, bott = pre[bott];
}

void workc (int root, int bott)
{
    ++squ, t.push (root, squ, 0);
    int tmp = bott, tot = pdis[root];
    while (bott != root) sum[bott] = tot, tot += dis[bott], bott = pre[bott];
    sum[squ] = tot;
    while (tmp != root)
        t.push (squ, tmp, min(sum[tmp], tot - sum[tmp])), tmp = pre[tmp];
}

void Build (int a, int lst)
{
    vis[a] = ++T;
    for (int i = g.head[a], nxt; ~i; i = g.nxt[i])
        if (nxt = g.to[i], (i^1) != lst)
        {
            if (vis[nxt] > vis[a]) continue;
            if (vis[nxt]) pdis[nxt] = g.w[i], bookc (nxt, a);
            else dis[nxt] = g.w[i], pre[nxt] = a, Build (nxt, i);
            if (cir[a] == -1) {cir[a] = 0; continue;}
            if (cir[a]) {workc (a, cir[a]), cir[a]=0; continue;}
            t.push (a, nxt, g.w[i]);
        }
}

void Init (int a, int fa)
{
    Pre[a][0] = fa, dep[a] = dep[fa] + 1;
    for (int i = 1; i <= LGS; i += 1) Pre[a][i] = Pre[Pre[a][i-1]][i-1];
    for (int i = t.head[a]; ~i; i = t.nxt[i])
        if (t.to[i] != fa)
            Deep[t.to[i]] = Deep[a] + t.w[i], Init(t.to[i], a);
}

int Lca (int a, int b, int& ta, int& tb)
{
    if (dep[a] > dep[b]) swap(a, b);
    for (int i = LGS; i >=0; i -= 1)
        if (dep[Pre[b][i]] >= dep[a])
            b = Pre[b][i];
    if (a == b) return a;
    for (int i = LGS; i >= 0; i -= 1)
        if (Pre[a][i] != Pre[b][i])
            a = Pre[a][i], b = Pre[b][i];
    ta = a, tb = b; return Pre[a][0];
}

int main (int argc, char const* argv[])
{
    IN(n),IN(m),IN(q);
    for (int i = 0, a, b, c; i < m; i += 1)
    {
        IN(a), IN(b), IN(c);
        g.push(a, b, c), g.push(b, a, c);
    }
    squ = n, Build(1, -1), Init(1, 0);
    while (q--)
    {
        int a, b, l, ta, tb;
        IN(a), IN(b), l = Lca(a, b, ta, tb);
        if (l <= n) printf ("%lld\n", Deep[a] + Deep[b] - (Deep[l] << 1));
        else
        {
            LL ans = Deep[a] + Deep[b] - Deep[ta] - Deep[tb];
            ans += min(abs(sum[ta] - sum[tb]), sum[l] - abs(sum[ta] - sum[tb]));
            printf("%lld\n", ans);
        }
    }
    return 0;
}