Title Link

Although LCA can also be written, dynamic trees are obviously much simpler to write (FOG) only from a personal point of view.

In our question, there is a hidden message that it must be a tree. It is said in the question that every two points must be linked to each other, or "a string" can be reached.

Next, you can directly go to the template of LCT and see the edge as a new point.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
#define MP3(a, b, c) MP(MP(a, b), c)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 8e4 + 7;
int N, M, Q, tot;
int c[maxN][2], fa[maxN], r[maxN], st[maxN];
ll val[maxN], s[maxN];
bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; }
void pushup(int x) { s[x] = s[c[x][0]] + s[c[x][1]] + val[x]; }
void pushr(int x) { swap(c[x][0], c[x][1]); r[x] ^= 1; }
void pushdown(int x)
{
    if(r[x])
    {
        if(c[x][0]) pushr(c[x][0]);
        if(c[x][1]) pushr(c[x][1]);
        r[x] = 0;
    }
}
void Rotate(int x)
{
    int y = fa[x], z = fa[y], k = c[y][1] == x;
    if(!isroot(y)) c[z][c[z][1] == y] = x;
    fa[x] = z;
    c[y][k] = c[x][k^1];
    fa[c[x][k^1]] = y;
    c[x][k^1] = y;
    fa[y] = x;
    pushup(y); pushup(x);
}
void Splay(int x)
{
    int y = x, z = 0;
    st[++z] = y;
    while(!isroot(y)) st[++z] = y = fa[y];
    while(z) pushdown(st[z--]);
    while(!isroot(x))
    {
        y = fa[x]; z = fa[y];
        if(!isroot(y)) (c[z][0] == y) ^ (c[y][0] == x) ? Rotate(x) : Rotate(y);
        Rotate(x);
    }
}
void access(int x)
{
    int y = 0;
    while(x)
    {
        Splay(x); c[x][1] = y;
        pushup(x);
        y = x; x = fa[x];
    }
}
void makeroot(int x)
{
    access(x); Splay(x);
    pushr(x);
}
int findroot(int x)
{
    access(x); Splay(x);
    while(c[x][0]) { pushdown(x); x = c[x][0]; }
    Splay(x);
    return x;
}
void split(int x, int y)
{
    makeroot(x);
    access(y); Splay(y);
}
void link(int x, int y)
{
    makeroot(x);
    if(findroot(y) != x) fa[x] = y;
}
inline void init()
{
    tot = 0;
    memset(s, 0, sizeof(s));
    memset(c, 0, sizeof(c));
    memset(r, 0, sizeof(r));
    memset(fa, 0, sizeof(fa));
}
char omg[10];
int main()
{
    while(scanf("%d%d", &N, &M) != EOF)
    {
        init();
        for(int i=1, u, v, w; i<=M; i++)
        {
            scanf("%d%d%d%s", &u, &v, &w, omg);
            val[N + i] = w;
            link(u, N + i);
            link(N + i, v);
        }
        scanf("%d", &Q);
        int x, y;
        while(Q--)
        {
            scanf("%d%d", &x, &y);
            if(x == y) { printf("0\n"); continue; }
            split(x, y);
            printf("%lld\n", s[y]);
        }
    }
    return 0;
}