Submission #61326148

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}

template<class G> struct HLD {
    using vi = vector<ll>;
#define sz(p) (p).size()
    G& g;
    ll n, id;
    vi siz, dep, down, up, nxt, par;
    void dfs_sz(ll i) {
        siz[i] = 1;
        if(sz(g[i]) > 1 && par[i] == g[i][0]) swap(g[i][0], g[i][1]);
        for(auto& j : g[i]) {
            if(j != par[i]) {
                dep[j] = dep[i] + 1;
                par[j] = i;
                dfs_sz(j);
                siz[i] += siz[j];
                if(siz[j] > siz[g[i][0]]) swap(j, g[i][0]);
            }
        }
    }
    void dfs_hld(ll i) {
        down[i] = id++;
        for(auto j : g[i]) if(j != par[i]) {
                nxt[j] = j == g[i][0] ? nxt[i] : j;
                dfs_hld(j);
            }
        up[i] = id;
    }
    HLD(G& g, ll v = 0) : g(g), n(sz(g)), id(0), siz(n), dep(n), down(n, -1), up(n, -1), nxt(n, v), par(n, v) {
        dfs_sz(v);
        dfs_hld(v);
    }
};

#include <atcoder/segtree>

ll op(ll a, ll b){
    return max(a, b);
}

ll e(){
    return 0ll;
}


// CITRUS CURIO CITY / FREDERIC
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> g_base(N);
    vector<vector<pair<int, ll>>> Gw(N);
    rep(i, 0, N - 1){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        a--, b--;
        c *= 3;
        g_base[a].emplace_back(b);
        g_base[b].emplace_back(a);
        Gw[a].emplace_back(b, c);
        Gw[b].emplace_back(a, c);
    }
    vector<ll> depth(N);
    {
        auto dfs = [&](auto self, int var, int pare) -> void {
            for (auto [a, b] : Gw[var]) if (pare != a){
                depth[a] = depth[var] + b;
                self(self, a, var);
            }
        };
        dfs(dfs, 0, -1);
    }
    HLD H(g_base);
    vector<ll> S(M), E(M), C(M), X(M), dp(M);
    rep(i, 0, M){
        cin >> S[i] >> E[i] >> C[i] >> X[i];
        C[i]--;
        S[i] *= 3, S[i]++;
        E[i] *= 3, E[i]--;
    }
    struct query {
        int type; // add is 0 or get is 1
        ll top_ind;
        ll x;
        ll y;
        int ind;
    };
    vector<query> p;
    rep(i, 0, M){
        ll ind = C[i];
        while (true){
            query tmp;
            tmp.ind = i;
            tmp.top_ind = H.nxt[ind];
            ll D = depth[ind];
            ll t = depth[C[i]] - depth[ind];
            // add
            tmp.type = 0;
            tmp.x = E[i] + t + D;
            tmp.y = E[i] + t - D;
            p.push_back(tmp);
            // get
            tmp.type = 1;
            tmp.x = S[i] - t + D;
            tmp.y = S[i] - t - D;
            p.push_back(tmp);
            if (H.nxt[ind] == 0) break;
            ind = H.par[H.nxt[ind]];
        }
    }
    sort(all(p), [&](query l, query r){
        if (l.top_ind != r.top_ind) return l.top_ind < r.top_ind;
        return l.x < r.x;
    });
    vector<int> L(N, -1);
    int len = p.size();
    rep(i, 0, len) if (L[p[i].top_ind] == -1){
        L[p[i].top_ind] = i;
    }
    vector<int> order(len);
    rep(i, 0, len) order[i] = i;
    sort(all(order), [&](int l, int r){
        return p[l].y < p[r].y;
    });
    atcoder::segtree<ll, op, e> seg(len);
    for (auto id : order){
        // add
        if (p[id].type == 0){
            seg.set(id, dp[p[id].ind]);
        }
        // get
        else{
            chmax(dp[p[id].ind], X[p[id].ind] + seg.prod(L[p[id].top_ind], id));
        }
    }
    cout << vec_max(dp) << "\n";
}

Submission Info

Judge Result