重軽分解により実装するとボトルネックとなる並列二分探索パートの計算量が\(O((M+Q) \log M \log^2 N)\)くらいですが、通ります。

解答例(C++,1465ms)

#include <bits/stdc++.h>
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define sz(c) ((int)(c).size())
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define endl "\n"
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1e18;
const int inf=1e9;
void cincout(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{
    int n;
    vector<T> dat;
    SegmentTree(int N){
        n=1;
        while(n<N) n*=2;
        dat.assign(n*2,e());
    }
    void set(int k,T x){
        k+=n;
        dat[k]=x;
        k>>=1;
        while(k){
            dat[k]=op(dat[k*2],dat[k*2+1]);
            k>>=1;
        }
    }
    T query(int l,int r){
        l+=n;
        r+=n;
        T sml=e(),smr=e();
        while(l<r){
            if(l&1) sml=op(sml,dat[l++]);
            if(r&1) smr=op(dat[--r],smr);
            l>>=1;
            r>>=1;
        }
        return op(sml,smr);
    }
};
ll op(ll a,ll b){ return a+b; }
ll e(){ return 0ll; }
int main(){
    cincout();
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<int>> g(n);
    vector<pair<int,int>> edge(n-1);
    FOR(i,n-1){
        int a,b;
        cin>>a>>b;
        --a,--b;
        g[a].push_back(b);
        g[b].push_back(a);
        edge[i]={a,b};
    }
    vector<P> seki(m);
    FOR(i,m){
        ll p,c;
        cin>>p>>c;
        --p;
        seki[i]={c,p};
    }
    sort(all(seki));
    vector<ll> s(q),t(q),x(q),y(q);
    FOR(i,q){
        cin>>s[i]>>t[i]>>x[i]>>y[i];
        --s[i],--t[i];
    }
    vector<int> dep(n),siz(n),ver,ind(n),a(n),par(n);
    auto cdd=[&](auto rec,int v,int p)->void{
        par[v]=p;
        siz[v]=1;
        for(auto& nv:g[v]){
            if(nv==p) continue;
            dep[nv]=dep[v]+1;
            rec(rec,nv,v);
            siz[v]+=siz[nv];
        }
    };
    dep[0]=0;
    cdd(cdd,0,-1);
    auto hld=[&](auto rec,int v,int p,int k)->void{
        ind[v]=ver.size();
        ver.push_back(v);
        a[v]=k;
        if(g[v].size()==1&&v!=0) return;
        int mx=0,ind=-1;
        FOR(i,g[v].size()){
            int nv=g[v][i];
            if(nv==p) continue;
            if(siz[nv]>mx){
                mx=siz[nv];
                ind=i;
            }
        }
        rec(rec,g[v][ind],v,k);
        FOR(i,g[v].size()){
            int nv=g[v][i];
            if(nv==p) continue;
            if(i!=ind) rec(rec,g[v][i],v,g[v][i]);
        }
    };
    hld(hld,0,-1,0);
    auto getpath=[&](int u,int v)->vector<pair<int,int>>{ // [l,r]...
        vector<pair<int,int>> ret;
        while(a[u]!=a[v]){
            if(dep[a[u]]<=dep[a[v]]){
                ret.push_back({ind[a[v]],ind[v]});
                v=par[a[v]];
            }else{
                ret.push_back({ind[a[u]],ind[u]});
                u=par[a[u]];
            }
        }
        ret.push_back({min(ind[u],ind[v]),max(ind[u],ind[v])});
        return ret;
    };
    FOR(i,n-1){
        if(dep[edge[i].first]<dep[edge[i].second]){
            swap(edge[i].first,edge[i].second);
        }
    }
    vector<int> ok(q),ng(q,m+1);
    FOR(tme,25){
        vector<int> mid(q);
        FOR(i,q) mid[i]=(ok[i]+ng[i])/2;
        vector<vector<int>> mp(m+1);
        FOR(i,q) mp[mid[i]].push_back(i);
        SegmentTree<ll,op,e> st(n);
        FOR(i,1,m+1){
            int tmp=edge[seki[i-1].second].first;
            st.set(ind[tmp],st.query(ind[tmp],ind[tmp]+1)+seki[i-1].first);
            for(auto& j:mp[i]){
                auto p=getpath(s[j],t[j]);
                ll sum=0;
                FOR(k,p.size()-1){
                    sum+=st.query(p[k].first,p[k].second+1);
                }
                sum+=st.query(p[sz(p)-1].first+1,p[sz(p)-1].second+1);
                if(sum<=y[j]){
                    ok[j]=mid[j];
                }else{
                    ng[j]=mid[j];
                }
            }
        }
    }
    vector<ll> ans(q);
    vector<vector<int>> mp(m+1);
    FOR(i,q) mp[ok[i]].push_back(i);
    SegmentTree<ll,op,e> st(n);
    FOR(i,m){
        int tmp=edge[seki[i].second].first;
        st.set(ind[tmp],st.query(ind[tmp],ind[tmp]+1)+1);
    }
    for(auto& j:mp[0]){
        auto p=getpath(s[j],t[j]);
        ll sum=0;
        FOR(k,p.size()-1) sum+=st.query(p[k].first,p[k].second+1);
        sum+=st.query(p[sz(p)-1].first+1,p[sz(p)-1].second+1);
        ans[j]=sum;
    }
    FOR(i,1,m+1){
        int tmp=edge[seki[i-1].second].first;
        st.set(ind[tmp],st.query(ind[tmp],ind[tmp]+1)-1);
        for(auto& j:mp[i]){
            auto p=getpath(s[j],t[j]);
            ll sum=0;
            FOR(k,p.size()-1) sum+=st.query(p[k].first,p[k].second+1);
            sum+=st.query(p[sz(p)-1].first+1,p[sz(p)-1].second+1);
            ans[j]=sum;
        }
    }
    FOR(i,q){
        if(ans[i]<=x[i]) cout<<x[i]-ans[i]<<'\n';
        else cout<<-1<<'\n';
    }
}