§ Desc.

Link.

给定一棵 $n$ 个节点的树, $m$ 个关键点 $\{a_m\}$, 和 $q$ 次询问 $l_i, r_i$. 每次询问点集 $\{a_l, \dots, a_r\}$ 在原树上虚树的大小.

$1 \leqslant n, q \leqslant 10^5$.

§ Sol.

考虑离线扫描线, 按 $l$ 排序. 每次扫描线加入一个点 $i$ 时, 就将 $a_i$ 到根节点这条路径上的节点的颜色覆盖为 $i$, 然后查询的答案就是树上所有颜色 $\leqslant r_i$ 的节点数减去 $a_l, \dots a_r$ 的 LCA 的深度.

具体实现, 先采用树剖, 颜色覆盖用 std::set 维护 (基于随机的颜色段均摊), 这里的复杂度是有保障的. 至于查询的第一部分, 使用树状数组维护即可. 第二部分可以用一个经典结论, 即若干个点的 LCA 等于 DFN 最小和最大的两点的 LCA, 用 RMQ 维护即可.

复杂度不会算, 但是跑得飞快.

struct RMQ {
    const int n;
    int t;
    vvi fi, fx;
    RMQ(const vi& v) : n(v.size()) {
        t = __lg(n)+1;
        fi = fx = vvi(t);
        fi[0] = fx[0] = v;
        for (int i=1;i<t;++i) {
            fi[i] = fx[i] = vi(n-(1<<i)+1);
            for (int j=0;j+(1<<i)<=n;++j) {
                fi[i][j] = min(fi[i-1][j], fi[i-1][j+(1<<(i-1))]);
                fx[i][j] = max(fx[i-1][j], fx[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int evalmin(int l, int r) {
        assert(0 <= l && l < r && r <= n);
        int k = __lg(r-l);
        return min(fi[k][l], fi[k][r-(1<<k)]);
    }
    int evalmax(int l, int r) {
        assert(0 <= l && l < r && r <= n);
        int k = __lg(r-l);
        return max(fx[k][l], fx[k][r-(1<<k)]);
    }
};
struct Interval {
    int l, r;
    mutable int v;
    Interval(int _l, int _r, int _v) : l(_l), r(_r), v(_v) {}
    bool operator<(const Interval& rhs) const { return l < rhs.l; }
};
set<Interval> odt;
int n, m, q, dfn[100100], times, ans[100100], dep[100100], fa[100100], t, rev[100100];
int son[100100], top[100100], sz[100100];
vi grp[100100];
void dfs(int u, int Fu) {
    dep[u] = dep[Fu]+1;
    fa[u] = Fu;
    sz[u] = 1;
    for (int v : grp[u])
        if (v != Fu) {
            dfs(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) son[u] = v;
        }
}
void dfs2(int u, int ct) {
    rev[dfn[u] = times++] = u;
    top[u] = ct;
    if (son[u] < n) dfs2(son[u], ct);
    for (int v : grp[u])
        if (v != fa[u] && v != son[u]) dfs2(v, v);
}
int glca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}
int bit[100100];
void add(int p, int x) {
    for (p++;p<=m;p+=p&-p) bit[p] += x;
}
int ask(int p) {
    int res = 0;
    for (;p;p-=p&-p) res += bit[p];
    return res;
}
///  @returns: [l, x), pointer at [x, r]
auto split(int x) {
    if (x == n) return odt.end();
    auto it = --odt.upper_bound(Interval(x, 0, 0));
    if (it->l == x) return it;
    auto [l, r, v] = *it;
    odt.erase(it);
    odt.emplace(l, x-1, v);
    return odt.emplace(x, r, v).fs;
}
void assign(int l, int r, int x) {
    auto ir = split(r+1), il = split(l);
    for (auto it=il;it!=ir;++it)
        if (it->v >= 0) add(it->v, it->l-it->r-1);
    odt.erase(il, ir);
    odt.emplace(l, r, x);
    add(x, r-l+1);
}
void access(int u, int x) {
    for (;u<n;u=fa[top[u]])
        assign(dfn[top[u]], dfn[u], x);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    t = __lg(n)+1;
    for (int i=1,u,v;i<n;++i) {
        cin >> u >> v;
        u--, v--;
        grp[u].pb(v), grp[v].pb(u);
    }
    fill(son, son+n, n);
    fa[n] = n;
    dfs(0, n);
    dfs2(0, 0);
    vi init(m);
    for (int i=0,x;i<m;++i) {
        cin >> x;
        x--;
        init[i] = dfn[x];
    }
    RMQ st(init);
    vt<vt<pii>> mnt(m);
    for (int i=0,l,r;i<q;++i) {
        cin >> l >> r;
        l--;
        assert(0 <= l && l < m);
        mnt[l].eb(r, i);
        int xl = st.evalmin(l, r);
        int xr = st.evalmax(l, r);
        ans[i] -= dep[glca(rev[xl], rev[xr])]-1;
    }
    odt.emplace(0, n-1, -1);
    for (int i=m-1;i>=0;--i) {
        access(rev[init[i]], i);
        for (auto&& [r, id] : mnt[i]) ans[id] += ask(r);
    }
    for (int i=0;i<q;++i) cout << ans[i] << "\n";
}

君子之交淡若水，因为淡所以不腻，才能持久。

—— 梁实秋 - 谈友谊