P1600 [NOIP2016] 天天爱跑步

p1600-[noip-2016-提高组]-天天爱跑步---洛谷">P1600 [NOIP 2016 提高组] 天天爱跑步 - 洛谷

1. 题面梗概

中译中：树上有 $M$ 个跑者，第 $i$ 个跑者在 $t=0$ 时从 $S_i$ 出发，匀速（每秒跑一条边）跑向 $T_i$。

每个节点 $u$ 都有一个观测员，他会在 $t = w_u$ 秒时进行观察。问每个观察员能看到多少个跑者。

$N, M \leq 3*10^5$

2. 逻辑推导

这题的暴力思路很简单，按照每个跑者跑一趟，然后统计节点，复杂度是 $O(NM)$，很显然直接就炸了。

正着不行，我们考虑转换视角，从观察者的角度切入，什么情况这个观察者能看到跑者呢？

2.1 路径

跑者从 $S \to T$ 的路径可以拆解为两条：$S \to Lca$ 的上行路径，以及 $Lca \to T$ 的下行路径。

我们推导一下观察者 $u$ 在 $w[u]$ 时间观察到跑者 $R$ 的条件。

• 上行路径：$w[u] = dep[S_{R}] -dep[u]$。
• 下行路径：$w[u] = (dep[s_{R}] - dep[Lca_{R}]) + (dep[u] - dep[Lca_{R}])$。

我们把两个柿子化简一下：

• 上行路径：$dep[S_{R}] = w[u] + dep[u]$
• 下行路径：$dep[S_{R}] - 2 * dep[LCA_{R}] = w[u] - dep[u]$

而每个节点 $u$ 的 $w[u], dep[u]$ 都是已知的，问题就转化为了，在 $u$ 节点的子树中，有哪些点是满足等式的。

2.2 树上差分

在普通的树上差分中，我们通过 +1/-1 来标记，但这里我们统计的是满足条件的点的个数，因此，我们标记的对象是一个值域桶。

对于路径 $R$ 来说，我们的差分打标记如下：

• 上行：cnt[ S ] += 1; cnt[ fa[Lca] ] -= 1;
• 下行：cnt[ Lca ] += 1; cnt[ T ] -= 1;

至于具体 +1/-1 是多少，根据我们前面的公式来处理。

2.3 结论

这基本上是 树上差分 问题的天花板了。这题用到了 DFS 入栈出栈差值 的小技巧，来模拟子树信息的离线统计。

3. 代码实现

▶

AcCode

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

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

struct Path { int s, t, lca, dist; } p[maxn];
struct Seg { int opt, val; };
vector< Seg > add[maxn], del[maxn];
vector< int > adj[maxn];
int dep[maxn], up[maxn][maxlg];
int w[maxn], ans[maxn];
int cnt1[maxn << 1], cnt2[maxn << 1];
int n, m;

void dfs_lca( int u, int p )
{
    dep[u] = dep[p] + 1, up[u][0] = p;
    for( int i = 1; i < maxlg; ++ i ) up[u][i] = up[up[u][i - 1]][i - 1];
    for( int v : adj[u] ) if( v != p ) dfs_lca( v, u );
}

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

void dfs_solve( int u, int p )
{
    int upVal = w[u] + dep[u];
    int downVal = w[u] - dep[u] + maxn;

    int pre1 = cnt1[upVal];
    int pre2 = cnt2[downVal];

    for( auto &[opt, val] : add[u] )
    {
        if( opt == 0 ) cnt1[val] ++;
        else cnt2[val + maxn] ++;
    }
    for( auto &[opt, val] : del[u] )
    {
        if( opt == 0 ) cnt1[val] --;
        else cnt2[val + maxn] --;
    }

    for( int v : adj[u] ) if( v != p ) dfs_solve( v, u );

    int suf1 = cnt1[upVal];
    int suf2 = cnt2[downVal];

    ans[u] = suf1 - pre1 + suf2 - pre2;
}

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

    cin >> n >> m;

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

    dfs_lca( 1, 0 );

    for( int i = 1; i <= n; ++ i ) cin >> w[i];

    for( int i = 1; i <= m; ++ i )
    {
        int s, t, lca, dist;
        cin >> s >> t;
        lca = get_lca( s, t );
        dist = dep[s] + dep[t] - 2 * dep[lca];
        // 0 -> up | 1 -> down
        add[s].push_back({ 0, dep[s] });
        if( up[lca][0] != 0 ) del[up[lca][0]].push_back({ 0, dep[s] });
        add[t].push_back({ 1, dist - dep[t] });
        del[lca].push_back({ 1, dist - dep[t] });
    }

    dfs_solve( 1, 0 );

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

4. 复盘

• 复杂度分析：$O(N \log N)$ 用于 LCA 预处理，$O(N+M)$ 用于差分统计。

• 碎碎念：这题的关键在于推导公式，把 变量 $S$ 和 常量 $u$ 分离，就很好处理了。还有一点麻烦的就是这个 $Lca$ 点，打标记的时候我把上升路径的撤销打在了 $fa[Lca]$ 上，这样可以避免 $Lca$ 点的重复计算。

• 关联笔记：LCA 体系 | 树上差分 | [[贡献法]]