#include <bits/stdc++.h>
#include "happy.h"
using namespace std;
vector<long long int> happy (int N, int Q, vector<int> u, vector<int> v, vector<int> h, vector<int> t, vector<int> l, vector<int> r) {
    vector<vector<pair<long long int, long long int>>> sus(300000);
    vector<pair<long long int, pair<long long int, long long int>>> vg;
    vector<long long int> ans;
    bool used[300000];
    bool open[300000];
    long long int w[300000]={};
    long long int cans, d=0;
    for(long long int i=0; i<N-1; i++) sus[u[i]].push_back({v[i], h[i]});
    vg.push_back({u[0], {u[0], 0}});
    while(d<vg.size()) {
        long long int prev=vg[d].first;
        long long int curr=vg[d].second.first;
        long long int currw=vg[d].second.second;
        if(curr==0) w[curr]=0;
        long long int cans=0, ex, one, a=w[prev], b=currw;
        for(long long int i=20; i>=0; i--) {
            long long int one=0;
            ex=exp2(i);
            if(ex<=a) {
                a-=ex;
                one++;
            }
            if(ex<=b) {
                b-=ex;
                one++;
            }
            if(one==1) cans+=ex;
        }
        w[curr]=cans;
        for(long long int i=0; i<sus[curr].size(); i++) {
            if(used[sus[curr][i].first]!=true) {
                vg.push_back({curr, {sus[curr][i].first, sus[curr][i].second}});
                used[sus[curr][i].first]=true;
            }
        }
        d++;
    }
    for(long long int i=0; i<Q; i++) {
        if(t[i]==1) for(long long int j=l[i]; j<=r[i]; j++) open[j]=true;
        else for(long long int j=l[i]; j<=r[i]; j++) open[j]=false;
        cans=0;
        for(int j=0; j<N; j++) {
                if(open[j]==true) {
                        for(long long int k=j+1; k<N; k++) {
                                if(open[k]==true) {
                                    long long int bans=0, one, ex, a=w[j], b=w[k];
                                    for(long long int i=20; i>=0; i--) {
                                        long long int one=0;
                                        ex=exp2(i);
                                        if(ex<=a) {
                                            a-=ex;
                                            one++;
                                        }
                                        if(ex<=b) {
                                            b-=ex;
                                            one++;
                                        }
                                        if(one==1) bans+=ex;
                                    }
                                    cans+=bans;
                                }
                        }
                }
        }
        v.push_back(cans);
    }

    return ans;
}
