13431.cpp

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define ll long long
using namespace std;

const ll INF = 1e9 + 7;
const ll DIV = 987654321;

const int maxn = 100010;
vector<pair<int,ll>> adj[maxn];

int subtree_size[maxn];
bool is_removed[maxn];

int get_subtree_size(int node, int parent = -1) {
	subtree_size[node] = 1;
	for (auto[child,w] : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		subtree_size[node] += get_subtree_size(child, node);
	}
	return subtree_size[node];
}

int get_centroid(int node, int tree_size, int parent = -1) {
	for (auto[ child, w] : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		if (subtree_size[child] * 2 > tree_size) {
			return get_centroid(child, tree_size, node);
		}
	}
	return node;
}


int n, q;
vector<ll> ans;
int h[101010];
ll par[18][101010], parn[18][101010];
void dfs(int cur, int prv){
    h[cur] = h[prv] + 1;
    for(auto[nxt, w] : adj[cur]){
        if(nxt == prv) continue;
        par[0][nxt] = w;
        parn[0][nxt] = cur;
        dfs(nxt, cur);
    }
}

ll dist(int a, int b){

    if(h[a] < h[b]) swap(a, b);
    ll ret = 0;
    for(int i = 17;i>=0;i--){
        if(h[parn[i][a]] >= h[b]){
            ret += par[i][a];
            a = parn[i][a];
        }
    }

    if(a == b) return ret;

    for(int i =17;i>=0;i--){
        if(parn[i][a] != parn[i][b]){
            ret += par[i][a] + par[i][b];
            a=parn[i][a];
            b=parn[i][b];
        }
    }
    ret += par[0][a] + par[0][b];
    return ret;
}


vector<array<int,2>> qry[101010];
vector<array<int,4>> vv[101010];


int go(int cur){
    int ct = get_centroid(cur, get_subtree_size(cur));
    is_removed[ct] = 1;
    int t = 0;
    vector<int> c;
    for(auto[i, w] : adj[ct]){ 
        if(is_removed[i]) continue;
        c.push_back(go(i));
    }

    auto& v = vv[ct];
    for(auto i : c){ 
        auto& u = vv[i];
        for(auto a : u) v.push_back({a[0], a[1], a[2], t});
        u.clear();
        t++;
    }

    for(auto[i, type]: qry[ct]){
        v.push_back({i, type, ct, t});
    }

    t++;

    vector<ll> val(t), cnt(t);
    sort(v.begin(), v.end());

     
    ll tv = 0, tc = 0;

    for(auto[i, type, nd, tg] : v){
        if(type == 1){
            tc++;
            cnt[tg]++;
            ll d=dist(ct, nd);
            tv+=d;
            val[tg]+=d;
        }
        else{
            ll d = dist(ct, nd);
            ans[i]+=tv-val[tg]+(tc-cnt[tg])*d;
        }
    }

    return ct;
}

bool ck[101010];

int main()
{
    fastio;
    cin >> n >> q;
    ans.resize(q, -1);
    for(int i =0 ;i < n - 1;i++){
        int a, b, w;
        cin >> a>> b >> w;
        a++,b++;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    
    for(int i =0 ;i < q;i++){
        int a, b;
        cin >> a>> b;
        b++;
        if(a == 1){
            if(ck[b] == 0) qry[b].push_back({i, a});
            ck[b] = 1;
        } 
        else qry[b].push_back({i, a}), ans[i] = 0;
        
    }
    dfs(1, 1);
    for(int i = 1;i<=17;i++){
        for(int j = 1;j<=n;j++){
            parn[i][j] = parn[i - 1][parn[i - 1][j]];
            par[i][j] = par[i - 1][j] + par[i - 1][parn[i - 1][j]];
        }
    }
    go(1);


    for(auto v: ans){
        if(v == -1) continue;
        cout << v << "\n";
    }
    
    

    return 0;
}