不清楚正解, 但树套树真的能过 (1800ms)

题目要求即为求满足如图所示的{a, b, p, q} 对数

即对于每一个{a, b} 都要快速求出 到 的路径上, 存在 所对应的 在 的子树里

首先想到树剖, 发现线段树维护的是一段区间内所有点的对应点在 的子树里的个数, 直接在树剖的新编号上跑树套树, 具体为在下标线段树上套一层权值线段树 (对应点编号即为值, 值域依然是下标范围。 或者理解为别的也可以, 能A就是王道)

的对应点就是 , 但可能有多个, 所以开一个 维护

子树里少标了一个 , 聪明的同学们脑补一下吧

alt

下面是代码

本来没想着能过, 结果卡着过去了, 1800ms

注意点：

  1. 树套树内外层真的很容易搞混

  2. 注意 存的东西也要都换成树剖的下标

  3. 动态开点, 不然空间会炸

  4. 可能只有我跳的坑 :

    树剖还没求完, 就用了树剖的下标, 与第二条相关

    内外层线段树左右区间搞混, wuwuwu~~

    还还没读进来, 就已经建树和跑树剖了

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 300010, M = 2 * N;

struct Node
{
    int l, r;
    int sum;
}tr[N * 20 * 20];

int L[4 * N], R[4 * N], T[4 * N];

int n, m, Q;
int h[N], e[M], ne[M], idx;
int id[N], cnt;
int dep[N], top[N], fa[N], sz[N], son[N];
vector<int> w[N], g[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void update(int u, int l, int r, int x)
{
    tr[u].sum ++ ;
    if(l == r) return ;
    int mid = l + r >> 1;
    if(x <= mid)
    {
        if(!tr[u].l) tr[u].l = ++ idx;
        update(tr[u].l, l, mid, x);
    }
    else
    {
        if(!tr[u].r) tr[u].r = ++ idx;
        update(tr[u].r, mid + 1, r, x);
    }
}

void build(int u, int l, int r)
{
    L[u] = l, R[u] = r, T[u] = ++ idx;
    for (int i = l; i <= r; i ++ )
        for (auto j : g[i])
            update(T[u], 1, n, j);
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

int query(int u, int l, int r, int pl, int pr)
{
    if (l >= pl && r <= pr) return tr[u].sum;
    else
    {
        int mid = l + r >> 1;
        int res = 0;
        if (pl <= mid && tr[u].l) res = query(tr[u].l, l, mid, pl, pr);
        if (pr > mid && tr[u].r) res += query(tr[u].r, mid + 1, r, pl, pr);
        return res;
    }
}

int get_ans(int u, int l, int r, int pl, int pr)
{
    if(L[u] >= l & R[u] <= r) return query(T[u], 1, n, pl, pr);
    int res = 0, mid = L[u] + R[u] >> 1;
    if(l <= mid) res = get_ans(u << 1, l, r, pl, pr);
    if(r > mid) res += get_ans(u << 1 | 1, l, r, pl, pr);
    return res;
}

void dfs1(int u, int p, int depth)
{
    dep[u] = depth, fa[u] = p, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == p) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if(sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int t)
{
    id[u] = ++ cnt, top[u] = t;
    if(!son[u]) return ;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void dfs3(int u)
{
    for (auto i : w[u]) g[id[u]].push_back(id[i]);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa[u]) continue;
        dfs3(j);
    }
}

int query_path(int u, int v, int a, int b)
{
    int res = 0;
    while (top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        res += get_ans(1, id[top[u]], id[u], a, b);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    res += get_ans(1, id[v], id[u], a, b);
    return res;
}

int main()
{
    memset(h, -1, sizeof h);
    
    scanf("%d%d%d", &n, &m, &Q);
    for (int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        w[a].push_back(b);
    }
    
    dfs1(1, -1, 1);
    dfs2(1, 1);
    dfs3(1);
    idx = 0;
    build(1, 1, n);
    
    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", query_path(1, a, id[b], id[b] + sz[b] - 1));
    }
    
    return 0;
}


/*

1

*/

总结： 一道比较板子的树套树, 但对代码能力真的要求真的不低, 没有什么思维含量与别出心裁的设计, 只要树套树掌握熟练, 这题就是个送分题