iY2xKx - Online C++ Compiler & Debugging Tool

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define MAX 100100
#define pb push_back

int n,q;
vector<tuple<int,int,int> > adj[MAX];
int head[MAX], w[MAX], depth[MAX], treesize[MAX], pos[MAX], parent[MAX], root[MAX], w1[MAX], a[MAX];
int cnt = 0, cur = 0;
int sum[(int)3e6], lc[(int)3e6], rc[(int)3e6];
ll d[MAX];

int build(int l, int r)
{
    int pos = ++cur;
    if(l == r){
        sum[pos] = 0;
        lc[pos] = -1;
        rc[pos] = -1;
        return pos;
    }else{
        int m = (l+r)>>1;
        sum[pos] = 0;
        lc[pos] = build(l,m);
        rc[pos] = build(m+1,r);
        return pos;
    }
}

int update(int l, int r, int po, int prev)
{
    int pos = ++cur;
    if(l == r){
        sum[pos] = sum[prev] + 1;
        lc[pos] = -1;
        rc[pos] = -1;
        return pos;
    }else{
        int m = (l+r)>>1;
        if(po <= m){
            lc[pos] = update(l,m,po,lc[prev]);
            rc[pos] = rc[prev];
            sum[pos] = sum[lc[pos]] + sum[rc[pos]];
        }else{
            rc[pos] = update(m+1,r,po,rc[prev]);
            lc[pos] = lc[prev];
            sum[pos] = sum[lc[pos]] + sum[rc[pos]];
        }
        return pos;
    }
}

int get(int nodl, int nodr, int l, int r, int u, int v)
{
    if(r < u || v < l) return 0;
    if(u <= l && r <= v) return nodr[sum] - nodl[sum];
    int m = (l+r)>>1;
    return get(lc[nodl],lc[nodr],l,m,u,v) + get(rc[nodl], rc[nodr],m+1,r,u,v);
}

void nhap()
{
    cin >> n >> q;
    for(int i = 0; i<n-1; i++){
        int a,b,c,d; cin >> a >> b >> c >> d;
        adj[a].pb(make_tuple(b,c,d));
        adj[b].pb(make_tuple(a,c,d));
    }
    parent[1] = 0;
    depth[1] = 0;
    w[1] = 0;
    d[1] = 0;
}

void dfs(int v)
{
    int index = -1;
    treesize[v] = 1;
    for(int i = 0; i< adj[v].size(); i++) if(get<0>(adj[v][i]) != parent[v]){
        int u = get<0>(adj[v][i]);
        parent[u] = v;
        w[u] = get<2>(adj[v][i]);
        w1[u] = get<1>(adj[v][i]);
        depth[u] = depth[v] + 1;
        d[u] = d[v] + get<1>(adj[v][i]);
        dfs(u);
        treesize[v] += treesize[u];
        if(index == -1 || treesize[u] > treesize[get<0>(adj[v][index])]) index = i;
    }
    if(index != 0 && index != -1) swap(adj[v][0], adj[v][index]);
}

void decompose(int v, int h)
{
    head[v] = h;
    pos[v] = ++cnt;
    for(tuple<int,int,int> x : adj[v]) if(get<0>(x) != parent[v]){
        if(get<0>(x) == get<0>(adj[v][0])) decompose(get<0>(x),h);
        else decompose(get<0>(x), get<0>(x));
    }
}

void process()
{
    dfs(1);
    decompose(1,1);
    root[0] = build(1,1e5);
    for(int i = 1; i<=n; i++) a[pos[i]] = w[i];
    for(int i = 1; i<=n; i++) root[i] = update(1,1e5,a[i],root[i-1]);
    while(q--){
        int u,v,k,y; cin >> u >> v >> k >> y;
        int _u = u;
        int _v = v;
        int dem = 0;
        while(head[u] != head[v]){
            if(depth[head[u]] < depth[head[v]]) swap(u,v);
            dem += get(root[pos[head[u]] -1], root[pos[u]],1,1e5,y,y);
            u = parent[head[u]];
        }
        if(depth[u] > depth[v]) swap(u,v);
        ll sum = d[_u] + d[_v] - 2*d[u];
        dem += get(root[pos[u]], root[pos[v]],1,1e5,y,y);
        dem = depth[_u] + depth[_v] - 2*depth[u] - dem;
        if(dem <= k){
            cout << sum << '\n';
        }else{
            cout << -1 << '\n';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    nhap();
    process();
}