P12577 [UOI 2021] 树上的强盗 题解

So_noSlack · 2026-11-11 14:39:01 · 题解

前置知识：重链剖分，树剖求 lca，线段树二分。

好题，部分分很有引导作用，下面我会一步步讲解如何通过部分分的提示想到正解。

首先看完题就会发现题目的描述太模糊了，我们考虑先形式化一下，实际上一次询问等价于求 u \to v 路径上满足 dis(u,x) + T \ge t_x 且 b \ne a_x 的离 u 最近的 x，直接统计是 O(nm) 的。可以通过子任务 2，再特判一下菊花图可通过子任务 1，有 16pts。

但是这跟正解没什么关系，我们接着考虑子任务 3，发现对于子任务 3 我们不需要考虑第一个条件了，因为它始终满足，于是只需要考虑 b \ne a_x，由于是链，我们可以线性递推出来 f_i 表示最小的 p 满足 a_{p \sim i} = a_i，以及 g_i 表示最大的 p 满足 a_{i \sim p} = a_i，有了 f_i,g_i 之后就可以查询 f_u 或者 g_u 做到 O(1) 回答，查询哪个取决于 u,v 的位置关系。可以通过子任务 3，拼上之前的分有 27pts。

但是这跟正解貌似依旧没什么关系，因为无法推广，我们接着考虑子任务 4，发现对于子任务 4 我们不需要考虑第二个条件了，于是只需考虑 dis(u,x) + T \ge t_x。这个式子无法直接维护，考虑移向并把 dis(u,x) 拆开，令 dis_x 表示 1 \to x 的距离，那么式子可化为 T \ge t_x - |dis_u - dis_x|，讨论一下大小关系可得到 T \pm dis_u \ge t_x \pm dis_x，两边同号。由于是链，而且不带修，我们发现可以用 st 表维护区间最小值，每次查询二分出来离 u 最近的不合法点即可，预处理 O(n \log n)，单次查询 O(\log n)，总复杂度为 O((n+m) \log n)。可以通过子任务 4，拼上之前的分有 45pts。

到这里我们会发现貌似有点眉目了，接着考虑子任务 5，也就是对于上面的做法考虑怎么加上 b \ne a_x 的限制。我们的目标就是不考虑 a_x = b 的 x，也就是把这样的 x 对应的 t_x 改为 \infty，只需要在上面做法的基础上支持带修即可，可以想到用线段树维护区间最小值。但是这样的话二分加线段树就是 O(\log^2 n) 的了，考虑在线段树上二分做到 O(\log n)，具体实现可参考代码。现在的问题就是，每次询问我都把 a_x = b 的 x 修改一遍，这样时间复杂度就炸完了。发现至多有 n 个不同的 b，我们只需要把询问离线下来，按 b 处理就好了，每个点最多修改两次，均摊时间复杂度为 O(m \log n)。可以通过子任务 5，拼上之前的分有 60pts。

到这里其实我们已经想出来正解了，剩下的一个操作就是套上一个重链剖分，使得我们可以做到树上修改、查询。需要注意的是，树上路径我们需要分成 u \to \text{lca}(u,v) \to v 两部分统计，因为树剖只能往上跳，实际上是分成 u 向 \text{lca}(u,v) 跳、v 向 \text{lca}(u,v) 跳两个过程，前者只要找到不合法的立刻返回，后者需要找到最靠近 \text{lca}(u,v) 的不合法点，所以要跳完全程。另外树剖求 lca 就不多说了，跟跳重链的过程区别不大。

#include<bits/stdc++.h>
#define db(x) cout << "#" << (#x) << ": " << (x) << "\n"
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define se second
#define pb push_back
using namespace std;
#define N 100005
#define inf 0x3f3f3f3f3f3f3f3f

bool _START_M;
ll n, m, a[N], t[N], fa[N], dfn[N], dn, rm[N], dis[N];
ll sz[N], son[N], top[N], dep[N], ans[N];
struct node { ll x, y, t, id; };
vector<node> q[N];
vector<pii> v[N];
vector<ll> h[N];
bool _END_M;

void dfs(ll x) {
    sz[x] = 1, dep[x] = dep[fa[x]] + 1;
    for(auto it : v[x]) if(it.fi != fa[x]) {
        ll y = it.fi, w = it.se;
        dis[y] = dis[x] + w, fa[y] = x, dfs(y), sz[x] += sz[y];
        if(sz[y] > sz[son[x]]) son[x] = y;
    }
}

void dfs(ll x, ll t) {
    dfn[x] = (++ dn), rm[dn] = x, top[x] = t; if(son[x]) dfs(son[x], t);
    for(auto it : v[x]) if(it.fi != fa[x] && it.fi != son[x]) dfs(it.fi, it.fi);
}

ll lca(ll x, ll y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    } 
    return (dep[x] > dep[y] ? y : x);
}

struct seg {
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid ((l + r) >> 1)
    ll t[N << 2];
    seg() { memset(t, 0x3f, sizeof t); }
    void upd(ll p, ll l, ll r, ll x, ll k) {
        if(l == r) { t[p] = k; return; }
        if(x <= mid) upd(ls, l, mid, x, k);
        else upd(rs, mid + 1, r, x, k);
        t[p] = min(t[ls], t[rs]);
    }
    ll qry(ll p, ll l, ll r, ll x, ll y, ll k, bool f) {
        if(x <= l && r <= y && t[p] > k) return -1;
        if(l == r) return (t[p] > k ? -1 : l);
        if(y <= mid) return qry(ls, l, mid, x, y, k, f);
        if(x > mid) return qry(rs, mid + 1, r, x, y, k, f);
        if(!f) {
            ll res = qry(ls, l, mid, x, y, k, f);
            if(~res) return res;
            return qry(rs, mid + 1, r, x, y, k, f);
        }
        else {
            ll res = qry(rs, mid + 1, r, x, y, k, f);
            if(~res) return res;
            return qry(ls, l, mid, x, y, k, f);
        }
    }
    #undef ls
    #undef rs
    #undef mid
} T1, T2;

ll qry(ll x, ll y, ll T) {
    ll _x = x, _y = y, z = lca(x, y);
    ll t = -1, _t;
    while(top[x] != top[z]) {
        t = T2.qry(1, 1, n, dfn[top[x]], dfn[x], T + dis[_x], 1);
        if(~t) return t; x = fa[top[x]];
    }
    t = T2.qry(1, 1, n, dfn[z], dfn[x], T + dis[_x], 1);
    if(~t) return t; T += (dis[_x] - dis[z]); 
    while(top[z] != top[y]) {
        _t = T1.qry(1, 1, n, dfn[top[y]], dfn[y], T - dis[z], 0);
        t = (~_t ? _t : t), y = fa[top[y]];
    }
    _t = T1.qry(1, 1, n, dfn[z], dfn[y], T - dis[z], 0);
    return (~_t ? _t : t);
}

void solution(ll tas) {
    cin >> n;
    rep(i, 2, n) { 
        ll x, w; cin >> x >> w; 
        v[x].pb({i, w}), v[i].pb({x, w}); 
    }
    dfs(1), dfs(1, 1);
    rep(i, 1, n) cin >> a[i], h[a[i]].pb(dfn[i]);
    rep(i, 1, n) cin >> t[i];
    cin >> m;
    rep(i, 1, m) { 
        ll x, y, b, t; cin >> x >> y >> b >> t; 
        q[b].pb({x, y, t, i}); 
    }
    rep(i, 1, n) { 
        ll x = dfn[i]; 
        T1.upd(1, 1, n, x, t[i] - dis[i]);
        T2.upd(1, 1, n, x, t[i] + dis[i]); 
    }
    rep(i, 1, n) {
        for(auto x : h[i - 1]) {
            ll id = rm[x];
            T1.upd(1, 1, n, x, t[id] - dis[id]); 
            T2.upd(1, 1, n, x, t[id] + dis[id]);
        }
        for(auto x : h[i]) T1.upd(1, 1, n, x, inf), T2.upd(1, 1, n, x, inf);
        for(auto it : q[i]) {
            ll res = qry(it.x, it.y, it.t);
            if(~res) res = rm[res];
            ans[it.id] = res;
        }
    }
    rep(i, 1, m) cout << ans[i] << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    double _START_T = clock();
    ll tas = 1; // cin >> tas;
    rep(i, 1, tas) solution(i);
    double _END_T = clock();
#ifdef LOCAL
    cerr << "\n--------------------------------RUN OVER\n";
    cerr << (&_START_M - &_END_M) / 1024 / 1024 << " MB used\n";
    cerr << _END_T - _START_T << " ms passed\n";
#endif
    return 0;
}