[Leaf] [P3629] 巡逻

p3629-[apio2010]-巡逻---洛谷">P3629 [APIO2010] 巡逻 - 洛谷

1. 题面梗概

中译中：给你一棵树，警察每天要走遍每一条边并回到起点。你可以建 1 条或 2 条新路（快捷径），问怎么建路能让警察每天跑的路程最少？（注意：新路必须走且只能走一次）。

2. 逻辑推导

我们考虑怎么修路能节省路程，很显然就是在原本树上直径的两个端点连一条捷径，那这就是个直径相关题目了。

2.1 $k = 1$

对于 $k = 1$ 的情况，很简单。原本 $n$ 个节点，一共要走 $2(n - 1)$ 条边，新增的边能少走 $L1 - 1$ 条边。（ $L1$ 为直径 ）

新的树上有了一个环，少走 $L1$ 条边，多走一条新路，所以是 $L1 - 1$。

2.2 $k = 2$

如果要再修一条呢？最简单的情况下，两条路形成的两条环不重合，那么就很简单了，第二个新边也是少走 $L2 - 1$ 条边。

但问题是：如果两个环重合了呢？

重叠部分的边，被省了 $2$ 次，意味着这条边从原本要走的 $2$ 次，被优化成了 $0$ 次。但这是不现实的，这条边在实际巡逻中是必须要走的。

这就意味着，在第二次建环的时候，这些重叠部分的边，反而产生了一个 $-1$ 的抵消收益。

重新理一下，本来每条边贡献是 $2$，来回各一趟，第一次建环收益算了它 $+1$，第二次建环收益减去它 $-1$，那不就是 $0$ 次了，跟最开始的推导结果一致。

这样转换后，再在原图上跑一次找直径，就可以得到预期的答案了。

2.3 结论

这是个直径性质的好问题，有两个好玩的点，第一个是这个边权从 $1 \to -1$ 的转换，另一个就是在带有负权边上查询直径，需要用到 DP。

3. 代码实现

▶

AcCode

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

const int maxn = 1e5 + 50;

struct Pre { int p, idx; } pre[maxn];

struct Edge { int v, w, rev; };
vector< Edge > adj[maxn];

int dist[maxn], from_node[maxn], from_edge[maxn];
int L1, L2, ed;
int dp[maxn];
int n, k;

void add_edge( int u, int v, int w )
{
    int idx_u = adj[u].size( );
    int idx_v = adj[v].size( );
    adj[u].push_back({ v, w, idx_v });
    adj[v].push_back({ u, w, idx_u });
}

void dfs( int u, int p, int d )
{
    dist[u] = d;
    if( d > L1 ) L1 = d, ed = u;

    for( int i = 0; i < adj[u].size( ); ++ i )
    {
        int v = adj[u][i].v;
        if( v == p ) continue;
        pre[v] = { u, i };
        dfs( v, u, d + 1 );
    }
}

void dfs_dp( int u, int p )
{
    dp[u] = 0;
    for( auto &e : adj[u] )
    {
        if( e.v == p ) continue;
        dfs_dp( e.v, u );
        L2 = max( L2, dp[u] + dp[e.v] + e.w );
        dp[u] = max( dp[u], dp[e.v] + e.w );
    }
}

void solve( )
{
    cin >> n >> k;
    for (int i = 1; i < n; ++ i )
    {
        int u, v;
        cin >> u >> v;
        add_edge( u, v, 1 );
    }

    L1 = -1;
    dfs( 1, 0, 0 );
    int u = ed;

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

    int cost = 2 * ( n - 1 ) - ( L1 - 1 );

    if( k == 1 )
    {
        cout << cost << '\n';
        return ;
    }

	// 边权取反
    for( int cur = v; cur != u; cur = pre[cur].p )
    {
        auto [p, idx] = pre[cur];
        adj[p][idx].w = -1;

        int r_idx = adj[p][idx].rev;
        adj[cur][r_idx].w = -1;
    }

    L2 = 0;
    dfs_dp( 1, 0 );
    cout << cost - ( L2 - 1 ) << '\n';
}

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

4. 复盘

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

• 碎碎念：这题我最开始是用链式前向星的，因为 vector 邻接表删边很麻烦，但是我真的不喜欢链式前向星，所以我用了一个 rev 反向边索引，来优化这个修改边权的过程，不用遍历整张表。

• 关联笔记：直径与重心 | [[树形DP体系]]