[Leaf] P4211 LCA

p4211-[lnoi2014]-lca---洛谷">P4211 [LNOI2014] LCA - 洛谷

1. 题面梗概

中译中：给出一棵 $n$ 个节点的有根树，$m$ 次询问。每次询问给出 $(l, r, z)$，求 $\sum_{i=l}^{r} dep[LCA(i, z)]$。结果对 $201314$ 取模。

2. 逻辑推导

直接枚举 $i$ 去求 LCA 肯定会炸，我们得挖掘 $dep[LCA(i, z)]$ 这个公式的性质，通过数学的方法去降维。

2.1 路径

$dep[LCA(i, z)]$ 到底是什么？它是 $LCA(i, z)$ 的深度，也就是从根节点到 $i$ 点和 $z$ 点路径上的公共节点数。

那么如果我们把 $i \to root$ 路径上的所有点权都 $+1$，那么 $dep[LCA(i, z)]$ 不就等于此时 $z \to root$ 路径上的点权和了吗？

利用这个转化我们就把原来的问题转化为了：

• 将 $i \in [l,r]$ 每个点到根的路径全部点权 $+1$。
• 查询 $z$ 到根的路径点权总和。

2.2 离线

询问区间 $[l,r]$ 是动态的，如果直接按顺序处理每个查询，我们需要频繁地在一个 已经加过某些点 的状态和 清空 的状态之间切换，或者就要使用复杂的可持久化数据结构（ 主席树+树剖 ）。

但是！这个贡献值是满足前缀和性质的：

$$Ans(l, r, z) = Query(0, r, z) - Query(0, l - 1, z)$$

其中 $Query( x, y, z )$ 表示把编号 $x \to y$ 的点到根路径全部 $+1$ 后，$z$ 到根的查询结果。

可以发现，$Query( x, y, z )$ 的状态只取决于 前 $x$ 个点是否已经加到树上。

2.3 排序

我们可以将每个查询 $(l, r, z)$ 拆成两个前缀任务：

• 在 $pos = r$ 处查询 $z$ 的路径和，结果记为正贡献。
• 在 $pos = l -1$ 处查询 $z$ 的路径和，结果记为负贡献。

接着用扫描线思路，将所有拆分出来的任务按照 $pos$ 从小到大排序。

我们只需要从 $0 \to n-1$ 遍历一遍节点，每次遍历到一个节点 $i$，就把它到根的路径 $+1$。

当遍历的指针到达某个任务的 $pos$ 时，直接执行该点的查询，由于 $pos$ 是递增的，所以我们不需要回溯或者撤销修改，只需要不断累积贡献即可。

2.3 树剖

在这个过程中，我们需要执行两种核心操作：

• 路径修改：将 $i \to root$ 路径上的所有点点权 $+1$。
• 路径查询：查询 $z \to root$ 路径上的点权和。

在树上处理 路径 到 区间 的映射，首选 树链剖分，配合线段树即可在 $O(\log^2n)$ 内完成修改和查询。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e4 + 50;
const int mod = 201314;

vector< int > adj[maxn];
int fa[maxn], dep[maxn], sz[maxn], son[maxn];
int top[maxn], dfn[maxn], rnk[maxn], timer;
ll ans[maxn];
int n, m;

struct Node {
    int l, r;
    ll sum, add;
} tr[maxn << 2];

#define ls u << 1
#define rs u << 1 | 1

void pushup( int u ) 
{
    tr[u].sum = (tr[ls].sum + tr[rs].sum) % mod;
}

void pushdown( int u ) 
{
    if( tr[u].add == 0 ) return ;
    tr[ls].sum = (tr[ls].sum + tr[u].add * (tr[ls].r - tr[ls].l + 1)) % mod;
    tr[rs].sum = (tr[rs].sum + tr[u].add * (tr[rs].r - tr[rs].l + 1)) % mod;
    tr[ls].add = (tr[ls].add + tr[u].add) % mod;
    tr[rs].add = (tr[rs].add + tr[u].add) % mod;
    tr[u].add = 0;
}

void build( int u, int l, int r )
{
    tr[u].l = l, tr[u].r = r;
    tr[u].add = 0;
    if( l == r ) 
    {
        tr[u].sum = 0;
        return ;
    }
    int mid = ( l + r ) >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
    pushup( u );
}

void modify( int u, int l, int r, int val )
{
    if( l <= tr[u].l && tr[u].r <= r )
    {
        tr[u].sum = (tr[u].sum + val * (tr[u].r - tr[u].l + 1)) % mod;
        tr[u].add = (tr[u].add + val) % mod;
        return ;
    }    
    pushdown( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) modify( ls, l, r, val );
    if( mid < r ) modify( rs, l, r, val );
    pushup( u );
}

ll query( int u, int l, int r )
{
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].sum;
    pushdown( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    ll res = 0;
    if( l <= mid ) res = ( res + query( ls, l, r ) ) % mod;
    if( r > mid ) res = ( res + query( rs, l, r ) ) % mod;
    return res;
}

void dfs1( int u, int p )
{
    fa[u] = p, dep[u] = dep[p] + 1, sz[u] = 1;
    for( int v : adj[u] ) 
    {
        if( v == p ) continue;
        dfs1( v, u );
        sz[u] += sz[v];
        if( sz[v] > sz[son[u]] ) son[u] = v;
    }
}

void dfs2( int u, int t )
{
    top[u] = t, dfn[u] = ++timer, rnk[timer] = u;
    if( son[u] == 0 ) return ;
    dfs2( son[u], t );
    for( int v : adj[u] ) 
    {
        if( v == fa[u] || v == son[u] ) continue;
        dfs2( v, v );
    }
}

void modify_path( int u, int v, int val )
{
    while( top[u] != top[v] )
    {
        if( dep[top[u]] < dep[top[v]] ) swap( u, v );
        modify( 1, dfn[top[u]], dfn[u], val );
        u = fa[top[u]];
    }
    if( dep[u] > dep[v] ) swap( u, v );
    modify( 1, dfn[u], dfn[v], val );
}

ll query_path( int u, int v )
{
    ll res = 0;
    while( top[u] != top[v] )
    {
        if( dep[top[u]] < dep[top[v]] ) swap( u, v );
        res = ( res + query( 1, dfn[top[u]], dfn[u] ) ) % mod;
        u = fa[top[u]];
    }
    if( dep[u] > dep[v] ) swap( u, v );
    res = ( res + query( 1, dfn[u], dfn[v] ) ) % mod;
    return res;
}

struct Task {
    int pos, z, id, opt;
    bool operator < ( const Task& oth ) const { return pos < oth.pos; }
};

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for( int i = 1; i < n; ++ i )
    {
        int p; cin >> p;
        adj[p + 1].push_back( i + 1 );
    }

    dfs1( 1, 0 );
    dfs2( 1, 1 );
    build( 1, 1, n );

    vector< Task > tasks;
    for( int i = 1; i <= m; ++ i )
    {
        int l, r, z; 
        cin >> l >> r >> z;
        l ++, r ++, z ++;
        tasks.push_back({ l - 1, z, i, -1 });
        tasks.push_back({ r, z, i, 1 });
    }

    sort( tasks.begin( ), tasks.end( ) );

    int cur = 0;
    for( auto [pos, z, id, opt] : tasks )
    {
        while( cur < pos )
        {
            cur ++;
            modify_path( 1, cur, 1 );
        }
        ll res = query_path( 1, z );
        ans[id] = ( ans[id] + res * opt + mod ) % mod;
    }

    for( int i = 1; i <= m; ++ i ) cout << ans[i] << '\n';
    return 0;
}

4. 复盘

• 复杂度分析：离线排序 $O(M \log M)$，扫描线过程包含 $N$ 次路径修改和 $2M$ 次路径查询，总复杂度 $O((N+M) \log^2 N)$。

• 碎碎念：这题如果不离线，就得强行上可持久化 HLD（也就是主席树套树剖），那空间和常数就太吓人了。还有一点是题目给的编号是从 0 开始的，转成 1 开始建树能省去很多判 0 的麻烦，也比较符合人的直觉。

• 关联笔记：树链剖分 | LCA 体系