题意分析

1. 图性质：
   • 村庄结构是一棵无向树（$n$个节点$n-1$条边且连通）
   • 任意两点间路径唯一（树的基本性质）
2. 操作要求：
   • 查询操作：计算当前节点到目标节点的路径边权和
   • 修改操作：动态更新指定边的权值

解题思路

1. 静态处理：
   • 通过$LCA$算法预处理每个节点的深度和到根节点的距离
   • 两点间距离公式：$dis(u,v) = dis(u) + dis(v) - 2 \times dis(lca(u,v))$
2. 动态维护：
   • 使用树链剖分将树分解为线性结构，通过线段树维护边权
   • 边权修改转化为对应$DFS$序的节点权值更新

实现步骤

1. 建树：
   • 构建邻接表存储树结构
   • 为每条边分配唯一编号
2. 预处理：
   • 进行$DFS$遍历计算父节点、深度、子树大小等
   • 实现$LCA$的倍增预处理
3. 消息处理：
   • 对消息$A$：计算当前节点$s$到目标$u$的路径和
   • 对消息$B$：更新对应边的权值并维护数据结构
4. 输出结果：
   • 对每个查询直接输出计算得到的路径和

代码实现

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int N = 2e5 + 10;

int n, q, s;

struct edge
{
    int v, w, id;
};

vector<edge> g[N];

int lpos[N << 2], rpos[N << 2], id[N << 2], idx, val[N << 2];

struct BIT
{
    int tr[N];
    int lowbit(int x)
    {
        return x & -x;
    }

    void update(int i, int c) // 位置x加c
    {
        for (; i <= (idx); i += lowbit(i))
            tr[i] += c;
    }

    int query(int i) // 返回前x个数的和
    {
        int res = 0;
        for (; i; i &= i - 1) // 等价于i -= lowbit(i)
            res += tr[i];
        return res;
    }
} t; // 树状数组板

int f[N][23], depth[N];
void get_depth(int u, int fa, int c) // 倍增LCA板 + 维护序列信息
{
    depth[u] = depth[fa] + 1, f[u][0] = fa;

    for (int i = 1; i <= 20; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for(int j = 0; j < g[u].size(); j ++)
    {
        int i = g[u][j].v, c = g[u][j].w, x = g[u][j].id;
        if (i == fa)
            continue;
        lpos[x] = id[i] = ++ idx; // 记录边与点在序列中的编号
        get_depth(i, u, c);
        rpos[x] = ++ idx;
    }
}

int Lca(int a, int b) // 倍增
{
    if (depth[a] > depth[b])
        swap(a, b);
    for (int i = 20; i >= 0; i--)
        if (depth[f[b][i]] >= depth[a])
            b = f[b][i];
    if (a == b)
        return a;
    for (int i = 20; i >= 0; i--)
        if (f[b][i] != f[a][i])
            b = f[b][i], a = f[a][i];
    return f[a][0];
}

edge make(int a, int b, int c)
{
    edge tmp;
    tmp.v = a, tmp.w = b, tmp.id = c;
    return tmp;
}

inline char get_char() // 加一点小小的卡常🤏
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read()
{
    int x = 0;
    char ch = get_char();
    while (ch < '0' || ch > '9')
        ch = get_char();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = get_char();
    return x;
}

int main()
{
    n = read(), q = read(), s = read();
    for (int i = 1; i < n; i++)
    {
        int a = read(), b = read(), w = read();
        g[a].push_back(make(b, w, i));
        g[b].push_back(make(a, w, i));
        val[i] = w;
    }

    get_depth(1, 0, 0); 
    
    for(int i = 1; i < n; i ++) // 差分树状数组
        t.update(lpos[i], val[i]), t.update(rpos[i], -val[i]);

    while (q--)
    {
        int op = read();
        if (op)
        {
            int u = read(), tmp = read();
            int l = lpos[u], r = rpos[u];
            t.update(l, tmp - val[u]), t.update(r, val[u] - tmp); // 因为是修改而不是增加需要改变一下
            val[u] = tmp;
        }
        else
        {
            int b = read();
            int lca = Lca(s, b);
            printf("%d\n", t.query(id[s]) + t.query(id[b]) - 2 * t.query(id[lca]));
            s = b; // 不要忘了结合题目，出发点是改变的
        }
    }
// cout << ' ';
    return 0;
}