模板：

struct Circle_Square_Tree {    const static int N = 2e4 + 10;    vector
    
     
       > G[N];    int dp[N], anc[N][18], n;    LL dis[N], cir[N]; //环的大小    bool vis[N];//记录到方点的最短距离是否经过回边    vector
      
        g[N];    int dfn[N], low[N], fa[N], cnt, tot;    int a[N];    inline void solve(int u, int v, int d) {        int cnt = 0;        LL sum = d;        for (int i = v; i != u; i = fa[i]) sum += dis[i] - dis[fa[i]], a[++cnt] = i;        a[++cnt] = u;        LL DIS = 0;        ++tot;        for (int i = cnt; i >= 1; --i) {            LL D = min(DIS, sum-DIS);            if(D == DIS) vis[a[i]] = true;            else vis[a[i]] = false;            G[a[i]].pb({tot, D});            G[tot].pb({a[i], D});            DIS += dis[a[i-1]]-dis[a[i]];        }        cir[tot] = sum;    }    inline void tarjan(int u, int o) {        fa[u] = o;        dfn[u] = low[u] = ++cnt;        for (int i = 0; i < g[u].size(); ++i) {            int v = g[u][i].fi;            int w = g[u][i].se;            if(v == o) 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(low[v] > dfn[u]) {                G[u].pb({v, w});                G[v].pb({u, w});            }        }        for (int i = 0; i < g[u].size(); ++i) {            int v = g[u][i].fi;            int w = g[u][i].se;            if(v == o) continue;            if(fa[v] != u && dfn[v] > dfn[u]) {                solve(u, v, w);            }        }    }    inline void dfs(int u, int o) {        anc[u][0] = o;        dp[u] = dp[o] + 1;        for (int i = 1; i < 18; ++i) anc[u][i] = anc[anc[u][i-1]][i-1];        for (int i = 0; i < G[u].size(); ++i) {            int v = G[u][i].fi;            LL w = G[u][i].se;            if(v == o) continue;            dis[v] = dis[u] + w;            dfs(v, u);        }    }    inline void init(int _n) {        tot = n = _n;        cnt = 0;        dis[0] = dp[1] = 0;        tarjan(1, 0);        dfs(1, 1);    }    inline int lca(int u, int v) {        if(dp[u] < dp[v]) swap(u, v);        for (int i = 17; i >= 0; --i) if(dp[anc[u][i]] >= dp[v]) u = anc[u][i];        if(u == v) return u;        for (int i = 17; i >= 0; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];        return anc[u][0];    }    inline int jump(int u, int lca) {        for (int i = 17; i >= 0; --i) if(dp[anc[u][i]] > dp[lca]) u = anc[u][i];        return u;    }    inline LL query(int u, int v) {        int l = lca(u, v);        if(l <= n) return dis[u]+dis[v]-2*dis[l];        int uu = jump(u, l), vv = jump(v, l);        LL d1 = dis[uu]-dis[l], d2 = dis[vv]-dis[l];        if(!vis[uu]) d1 = cir[l]-d1;        if(!vis[vv]) d2 = cir[l]-d2;        return dis[u]-dis[uu]+dis[v]-dis[vv]+min(abs(d1-d2), cir[l]-abs(d1-d2));    }}CST;