Submission #62876122

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using i64 = long long;

/*
 *  永続セグメント木の実装
 */
struct Val { i64 sum=0; int cnt=0; };
Val operator+(Val l, Val r){ return { l.sum + r.sum, l.cnt + r.cnt }; }
struct Node { int l, r; Val sum; };
Node A[100000 * 20 * 3];
int nodecnt = 0;
Val nodesum(int i){ return i < 0 ? Val() : A[i].sum; }
int newMidNode(int l, int r){
    int p = nodecnt++;
    A[p].l = l; A[p].r = r;
    A[p].sum = nodesum(l) + nodesum(r);
    return p;
}
int newLeafNode(Val x){
    int p = nodecnt++;
    A[p].l = A[p].r = -1;
    A[p].sum = x;
    return p;
}
int constructSeg(int N){
    if(N == 0) return -1;
    if(N == 1) return newLeafNode(Val());
    return newMidNode(constructSeg(N/2), constructSeg((N+1)/2));
}
int updateSeg(int i, int l, int r, int p, Val val){
    if(l + 1 == r) return newLeafNode(val);
    int m = (l+r)/2;
    if(p < m) return newMidNode(updateSeg(A[i].l, l, m, p, val), A[i].r);
    return newMidNode(A[i].l, updateSeg(A[i].r, m, r, p, val));
}


int N, M, Q;
vector<int> bfs;
vector<int> parent;
vector<int> edgetowhere;

vector<int> segs;

/*
 *  根付き木としたときの各頂点の親を得る
 *  BFS 順を得る
 */
void inputTree(){
    vector<int> A(N-1), B(N-1);
    vector<vector<int>> E(N);
    rep(i,N-1){
        int u,v; cin >> u >> v; u--; v--;
        E[u].push_back(i);
        E[v].push_back(i);
        A[i] = u; B[i] = v;
    }
    bfs.assign(N, 0);
    parent.assign(N, -1);
    int p = 1;
    rep(i,N){
        int v = bfs[i];
        for(int e : E[v]) if(parent[v] != e){
            int w = A[e] ^ B[e] ^ v;
            bfs[p++] = w;
            parent[w] = e;
        }
    }
    edgetowhere.resize(N-1);
    rep(i,N) if(i != 0) edgetowhere[parent[i]] = i;
    rep(i,N) if(i!=0) parent[i] = A[parent[i]] ^ B[parent[i]] ^ i;
}

/*
 *  関所の情報を読み込み、永続セグメント木を構築
 */
void inputGates(){
    vector<vector<int>> gates(N);
    vector<pair<int, int>> gatesize(M);
    rep(i,M){
        int e, x; cin >> e >> x; e--;
        int p = edgetowhere[e];
        gates[p].push_back(i);
        gatesize[i] = { x, i };
    }
    sort(gatesize.begin(), gatesize.end());
    vector<int> ord(M);
    rep(i,M) ord[gatesize[i].second] = i;

    segs.assign(N, -1);
    segs[0] = constructSeg(M);
    for(int v : bfs) if(v != 0){
        int w = parent[v];
        int seg = segs[w];
        for(int gate : gates[v]){
            int idx = ord[gate];
            int sz = gatesize[idx].first;
            seg = updateSeg(seg, 0, M, idx, {sz,1});
        }
        segs[v] = seg;
    }
}

/*
 *  LCA の計算
 */
vector<vector<int>> PP;
vector<int> depth;
int PPD = 16;
void pptable(){
    PP.assign(PPD+1, vector<int>(N));
    PP[0] = parent;
    PP[0][0] = 0;
    rep(d,PPD) rep(i,N) PP[d+1][i] = PP[d][PP[d][i]];
    depth.assign(N, 0);
    for(int i : bfs) if(i != 0) depth[i] = depth[parent[i]] + 1;
}
int lca(int u, int v){
    if(depth[u] > depth[v]) swap(u, v);
    for(int d=PPD; d>=0; d--) if((depth[v] - depth[u]) & (1 << d)) v = PP[d][v];
    if(u == v) return u;
    for(int d=PPD; d>=0; d--) if(PP[d][u] != PP[d][v]){ u = PP[d][u]; v = PP[d][v]; }
    return parent[u];
}

/*
 *  質問を 1 つ処理
 */
int minGold(vector<pair<int, int>> I, i64 silv){
    int ans = 0;
    int l = 0, r = M;
    while(l + 1 < r){
        int m = (l+r)/2;
        i64 suml = 0;
        for(auto i : I) suml += nodesum(A[i.first].l).sum * i.second;
        if(suml <= silv){
            silv -= suml;
            for(auto& i : I) i.first = A[i.first].r;
            l=m;
        }
        else{
            for(auto i : I) ans += nodesum(A[i.first].r).cnt * i.second;
            for(auto& i : I) i.first = A[i.first].l;
            r=m;
        }
    }
    i64 sumx = 0;
    for(auto i : I) sumx += nodesum(i.first).sum * i.second;
    if(sumx > silv) for(auto i : I) ans += nodesum(i.first).cnt * i.second;
    return ans;
}

int main(){
    std::cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    inputTree();
    inputGates();
    pptable();
    rep(q,Q){
        int s, t, x; i64 y; cin >> s >> t >> x >> y; s--; t--;
        int g = lca(s, t);
        int gold = minGold({ {segs[s],1}, {segs[t],1}, {segs[g],-2} }, y);
        if(gold > x) cout << "-1\n"; else cout << (x-gold) << '\n';
    }
    return 0;
}

Submission Info

Judge Result