复杂度就是 $O(qlogn)$ 但由于人比较傻，常数特别大，导致第二个点就 TLE。希望有大佬帮忙卡下常。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
/*
开始写：
2025.8.2 15:35
开始调试时间：
2025.8.2 17:35：
1. pair没写<int, int> 
2. New函数没返回 
3. update加了参数忘记传递
4. 忘判了 {-1, 1} 
5. long long - > MLE
6. 更新的时候 false - > true 
7. q + 1个颜色 
8. Tc2初始时 update 
9. st表范围初始值 
10. long long 没改完 
11. dep 和 dis 混淆 
*/
const int N = 500015, M = 500015, LGn = 20;
int LG2[N];
int n, q, C;
struct Graph {
    struct edge{
        int u, v, w;
        int nxt;
    };
    edge edges[M];
    int head[N], cnt = 0;
    int fa[N], dfn_st[N], id[N], tim;
    int dep[N];
    long long Dis[N];
	int st[N][LGn];
    void add(int u, int v, int w) {
        edges[++cnt] = edge{u, v, w, head[u]};
        head[u] = cnt;
    }
    void clear() {
        memset(head, 0, sizeof(head));
        cnt = 0; tim = 0;
    }   
    void dfs(int x, int f, long long dist, int depth) {
        fa[x] = f; dep[x] = depth; Dis[x] = dist;
        id[x] = ++tim;
        dfn_st[tim] = x;
        for(int i = head[x]; i; i = edges[i].nxt) {
            int to = edges[i].v;
            if(to == f) continue;
            dfs(to, x, dist + edges[i].w, depth + 1);
        }
    }
    int dep_min(int x, int y) {
        if(dep[x] < dep[y]) return x;
        else return y;
    }
    void init_LCA() {
        dfs(1, 0, 0, 1);
        for(int i = 1; i <= n; ++i) st[i][0] = dfn_st[i];
        
        for(int i = 1; (1 << i) <= n; ++i) {
            for(int j = 1; j + (1 << i) - 1 <= n; ++j) {
                st[j][i] = dep_min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
            }
        }
        return;
    }
    int LCA(int x, int y) {
        if(x == y) return x;
        x = id[x], y = id[y];
        if(x > y) std::swap(x, y);
        ++x;
        int len = LG2[y - x + 1];
        return fa[
            dep_min(
                st[x][len],
                st[y - (1 << len) + 1][len]
            )   
        ];
    }
    long long dis(int x, int y) {
        return Dis[x] + Dis[y] - 2 * Dis[LCA(x, y)];
    }
}G;


struct Query{
    int tp;
    int x, c, d;
    int num;
}Q[N];
struct node_c{
    int lson, rson;
    std::pair<int, int> u;
    node_c() {
        lson = rson = 0;
        u = std::make_pair(-1, -1);
    }
};

node_c nodes_c[N * LGn * 2];
int ind = 0, root[N];
inline std::pair<int, int> Max(std::pair<int, int> a, std::pair<int, int> b) {
	bool ma, mb;
	ma = (a.first == -1) || (a.second == -1);
	mb = (b.first == -1) || (b.second == -1);
    if(ma && mb) return std::make_pair(-1, -1);
    else if(ma) return b;
    else if(mb) return a;
    
    if(G.dis(a.first, a.second) > G.dis(b.first, b.second)) return a;
    else return b;
}
struct Seg_tree_C{
    inline int New() {
        ++ind;
        nodes_c[ind] = node_c();
        return ind;
    }
    void update(int k, bool del, int x, int l = 1, int r = n) {
        if(l == r) {
            if(del)
                nodes_c[x].u = std::make_pair(-1, -1);
            else   
                nodes_c[x].u = std::make_pair(k, k);
            return;
        }
        int mid = (l + r) / 2;
        if(k <= mid) {
            if(nodes_c[x].lson == 0) 
                nodes_c[x].lson = New();
            update(k, del, nodes_c[x].lson, l, mid);
        }
        else {
            if(nodes_c[x].rson == 0) 
                nodes_c[x].rson = New();
            update(k, del, nodes_c[x].rson, mid + 1, r);
        }
        std::pair<int, int> v1 = nodes_c[nodes_c[x].lson].u,
        v2 = nodes_c[nodes_c[x].rson].u;
        nodes_c[x].u = Max(
            Max(std::pair<int, int>{v1.first, v2.first}, 
            std::pair<int, int>{v1.first, v2.second}), 
            Max(std::pair<int, int>{v1.second, v2.first}, 
            std::pair<int, int>{v1.second, v2.second})
        );
        nodes_c[x].u = Max(
            nodes_c[x].u,
            Max(v1, v2)
        );
    }
    std::pair<int, int> query(int x) {
        return nodes_c[root[x]].u;
    }
}Tc; //Tree_color

struct Seg_Tree_C2
{
    struct node_c2 {
        std::pair<int, int> far, nsa_far;
        node_c2() {
            far = std::pair<int, int>{-1, -1};
            nsa_far = std::pair<int, int>{-1, -1};
        }
    };   
    node_c2 T2[N << 2];
    void clear(int x, int l, int r) {
        T2[x] = node_c2();
        if(l == r) return;
        int mid = (l + r) / 2;
        node_c2 &lson = T2[x << 1];
        node_c2 &rson = T2[(x << 1) + 1];
//        if(!(lson.far.first == -1 && lson.far.second == -1)) 
		clear(x << 1, l, mid);
//        if(!(lson.far.first == -1 && lson.far.second == -1)) 
		clear((x << 1) + 1, mid + 1, r);
        return;
    }
    void update(int k, int x = 1, int l = 1, int r = q + 1) {
        if(l == r) {
            T2[x].nsa_far = std::make_pair(-1, -1);
            T2[x].far = Tc.query(l);
            return;
        }
        int mid = (l + r) / 2;
        if(k <= mid) update(k, (x << 1), l, mid);
        if(k > mid) update(k, (x << 1) + 1, mid + 1, r);
        auto u1 = T2[x << 1].far, v1 = T2[x << 1].nsa_far,
        u2 = T2[(x << 1) + 1].far, v2 = T2[(x << 1) + 1].nsa_far;
        T2[x].far = Max(
            Max(u1, u2),
            Max(
                Max(std::pair<int, int>{u1.first, u2.first}, 
                std::pair<int, int>{u1.first, u2.second}), 
                Max(std::pair<int, int>{u1.second, u2.first}, 
                std::pair<int, int>{u1.second, u2.second})
            )
        );
        T2[x].nsa_far = Max(
            Max(v1, v2),
            Max(
                Max(std::pair<int, int>{u1.first, u2.first}, 
                std::pair<int, int>{u1.first, u2.second}), 
                Max(std::pair<int, int>{u1.second, u2.first}, 
                std::pair<int, int>{u1.second, u2.second})
            )
        );
    }
    long long query() {
        auto u = T2[1].nsa_far;
        if(u.first == -1 || u.second == -1) return 0;
        return G.dis(u.first, u.second);
    }
}Tc2;
int Color[N];
void init() {
    ind = 0;
    memset(Color, 0, sizeof(Color));
    G.clear();
}
inline int read() {
	int s = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
	return s;
}
void solve(){
//	printf("NEW test \n"); 
    init();
//    scanf("%d%d", &q, &C);
	q = read(); C = read();
    n = 1;
    for(int i = 1; i <= q; ++i) {
        int tp, x, c, d;
//        scanf("%d", &tp);
		tp = read();
        if(tp == 0) {
//            scanf("%d%d%d", &x, &c, &d);
			x = read(); c = read(); d = read();
            ++n; 
            Q[i] = Query{tp, x, c, d, n};
            G.add(x, n, d);
        }
        else {
//            scanf("%d%d", &x, &c);
			x = read(); c = read();
            Q[i] = Query{tp, x, c, 0, x};
        }
    }
    for(int i = 1; i <= q + 1; ++i) 
		root[i] = Tc.New();
    G.init_LCA();
    Tc2.clear(1, 1, q + 1);
    
    Color[1] = C;
    Tc.update(1, false, root[C]);
    Tc2.update(C);
//    printf("dis %d %d = %lld\n", 5, 3, G.dis(5, 3));
    for(int i = 1; i <= q; ++i) {
        if(Q[i].tp == 0) {
            Tc.update(Q[i].num, false, Q[i].c);
            Tc2.update(Q[i].c);
            Color[Q[i].num] = Q[i].c;
        }
        else {
            Tc.update(Q[i].num, true, root[Color[Q[i].num]]);
            Tc.update(Q[i].num, false, root[Q[i].c]);
            Tc2.update(Color[Q[i].num]);
            Tc2.update(Q[i].c);
            Color[Q[i].num] = Q[i].c;
        }
        printf("%lld\n", Tc2.query());
//        if(i % 10000 == 0)
    }
//    while(1) {
//        int x, y;
//        scanf("%d%d", &x, &y);
//        printf("%d\n", G.dis(x, y));
//    }
}
void initLg2() {
    LG2[1] = 0;
    for(int i = 2; i < N; ++i) 
        LG2[i] = LG2[i >> 1] + 1;
    return;
}
int main(){
//	freopen("dat.in", "r", stdin); 
//	freopen("my.out", "w", stdout); 	
    initLg2();
     int t;
     scanf("%d", &t);
     while(t--)
         solve();
    return 0;
}
/*
1
14 1
0 1 3 9
*/