[Leaf] [P3258] 松鼠的新家

p3258-[jloi2014]-松鼠的新家---洛谷">P3258 [JLOI2014] 松鼠的新家 - 洛谷

1. 题面梗概

中译中：松鼠要按顺序访问一串房间 $a_1 \to a_2 \to \dots \to a_n$。每到一个目的地（除了最后终点 $a_n$）都要停下来吃个糖。问每个房间最后分别被经过了多少次。

2. 逻辑推导

注意到，树上路径修改，统计点权，所以我们转向 树上点差分 角度解决这题。

2.1 点差分

在树上，如果我们要将路径 $(u, v)$ 上所有点的点权 $+1$。

那么我们将 diff[u] += 1; diff[v] += 1;，接下来这两点汇聚在 $LCA(u, v)$ 上，由于两点各贡献了一个 $+1$，此时 $LCA$ 变成了 $+2$，所以我们 diff[lca] -= 1。

但是，为了防止这个差分接着往根节点串，我们再加一条操作 diff[ fa[lca] ] -= 1;。

2.2 重叠

注意到这些路径不是独立的，而是连续的。$a_{1} \to a_{2}$ 修改了一次 $a_{2}$，而 $a_{2} \to a_{3}$ 又修改了一次 $a_{2}$，而 $a_{2}$ 这个点实际上只经过了一遍，所以我们要再处理去重。

2.3 结论

这是个标准的 树上点差分 问题。

3. 代码实现

▶

AcCode

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

const int maxn = 3e5 + 50;
const int maxlg = 20;

int fa[maxn][maxlg];
int dep[maxn];
int dif[maxn];
int sum[maxn];
int n;
vector<int> adj[maxn];

void dfs( int u, int father ) 
{
    fa[u][0] = father;
    dep[u] = dep[father] + 1;
    for( int v : adj[u] )
    {
        if( v != father )
            dfs( v, u );
    }
    return ;
}

void stInit( )
{
    for( int j = 1; j < maxlg; ++ j )
        for( int i = 1; i <= n; ++ i )
            fa[i][j] = fa[ fa[i][j-1] ][j-1];
    return ;
}

int getlca( int u, int v )
{
    if( dep[u] < dep[v] ) swap( u, v );
    int diff = dep[u] - dep[v];
    for( int i = 0; (1 << i) <= diff; ++ i )
    {
        if( (1 << i) & diff )
            u = fa[u][i];
    }
    if( u == v ) return u;
    for( int i = maxlg - 1; i >= 0; -- i )
    {
        if( fa[u][i] != fa[v][i] )
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void getsum( int u, int father )
{
    sum[u] = dif[u];
    for( int v : adj[u] )
    {
        if( v != father )
        {
            getsum( v, u );
            sum[u] += sum[v];
        }
    }
}

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

    cin >> n;
    vector<int> a(n + 1);
    for( int i = 1; i <= n; ++ i )
        cin >> a[i];
    
    for( int i = 1; i <= n-1; ++ i )
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    dfs( 1, 0 );
    stInit( );

    int u = a[1];
    for( int i = 2; i <= n; ++ i )
    {
        int v = a[i];
        int rt = getlca( u, v );
        dif[u] ++; dif[v] ++;
        dif[rt] --; dif[ fa[rt][0] ] --;
        u = v;
    }
    
    getsum( 1, 0 );

    for( int i = 2; i <= n; ++ i )
    {
        sum[ a[i] ] --;
    }

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

4. 复盘

• 复杂度分析：$O(N \log N)$ 。

• 碎碎念：注意到这个边界的特殊处理即可。然后再理解 点差分 和 边差分 的区别。

• 关联笔记：LCA 体系 | 树上差分