[Leaf] [P1099] 树网的核

p1099-[noip-2007-提高组]-树网的核---洛谷">P1099 [NOIP 2007 提高组] 树网的核 - 洛谷

1. 题面梗概

中译中： 在树的直径上选一段长度不超过 $s$ 的路径（称为“核”），让全树离这段路径最远的点尽可能近。求这个最小的最远距离（偏心距）。

2. 逻辑推导

首先这是个直径问题。我们考虑如何取这个 “核”。

对于直径上选取的 "核" $F = [i, j]$，这个偏心距有三个来源：

• 直径外：直径上所有点向外延伸的“枝条”长度的最大值。

• 直径内左侧：端点 $A$ 到 $F$ 左端点 $i$ 的距离，即 $dist( A, i )$。

• 直径内右侧：端点 $B$ 到 $F$ 右端点 $j$ 的距离，即 $dist( B, j )$。

公式: $ECC(F) = \max( max\_branch, dist(A, i), dist(B, j) )$。

2.1 优化

虽然本题 $N \leq 300$，随便 $n^3$ 暴力枚举，但我们还是要有点职业操守的（bushi。

注意到 "核" 必须在直径上，而且是一段连续的区间，不妨采用双指针维护，我们再确定一下是否符合单调性。

$dist( A, i )$ 随着 $i$ 增大而增大，$dist( B, j )$，随着 $j$ 增大而减小，很好，满足条件，跑一遍双指针即可。

2.2 结论

这是一道利用直径线性性质 + 双指针优化的题目，难点在于理解这个偏心距和核的定义。

3. 代码实现

▶

AcCode

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

const int maxn = 5e4 + 50;
const int inf = 0x3f3f3f3f;

struct Edge { int v, w; };
vector< Edge > adj[maxn];
int dist[maxn], fa[maxn], sz[maxn];
int disu[maxn], disv[maxn];
bool on_path[maxn];
int n, s, max_dist, ed;

void dfs( int u, int p, int d )
{
    dist[u] = d;
    fa[u] = p;

    if( d > max_dist ) max_dist = d, ed = u;

    for( auto [v, w] : adj[u] )
    {
        if( v == p ) continue;
        dfs( v, u, d + w );
    }
}

int dfs_branch( int u, int p )
{
    int res = 0;
    for( auto [v, w] : adj[u] )
    {
        if( v == p || on_path[v] ) continue;
        res = max( res, dfs_branch( v, u ) + w );
    }
    return res;
}

void solve( )
{
    cin >> n >> s;

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

    max_dist = 0; 
    dfs( 1, 0, 0 );
    int u = ed;
    max_dist = 0; 
    dfs( u, 0, 0 );
    int v = ed;

    vector< int > paths;
    for( int cur = v; cur != 0; cur = fa[cur] )
    {
        on_path[cur] = true;
        paths.push_back( cur );
    }
    reverse( paths.begin( ), paths.end( ) );

    int max_branch = 0;
    for( int cur : paths ) max_branch = max( max_branch, dfs_branch( cur, 0 ) );

    int ans = inf;
    int m = paths.size( );

    for( int k = 0; k < m; ++ k )
    {
        disu[k] = dist[paths[k]];
        disv[k] = dist[v] - disu[k];
    }

    for( int i = 0, j = 0; i < m; ++ i )
    {
        while( j + 1 < m && disu[j + 1] - disu[i] <= s ) j ++;
        int ecc = max( max_branch, max( disu[i], disv[j] ) );
        ans = min( ans, ecc );
    }

    cout << ans << '\n';
}

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

4. 复盘

• 复杂度分析：$O( N )$。DFS 和 双指针都是 $O(N)$。

• 碎碎念：所有非直径分支的贡献是固定的，这意味着可以优化，也就是只维护最大值，否则这个复杂度可能就变成 $O(N^3)$，虽然能跑，但是结合双指针的 $O(N)$ 线性复杂度不香吗？

• 关联笔记：直径与重心 | 双指针