题解：P12747 [POI 2016 R3] 巡游 Parade

喵。

知识点：图论，动态规划。

---

$\textup{Description}$

给定一棵树，求其起点不能与终点相同的一条简单路径上的每个点未被路径使用的边的最大总和。

---

$\textup{Solution}$

不想看弱智的我推式子可以直接看“最后”那块。

首先，观察到一个在路径上的点有两种贡献情况。

• 当前是段点（路径结束点），那么使用了一条路径上的边，贡献为其入度减一。
• 不是，则使用了两条边，同理贡献为入度减二。

相加得到总路障数应当为：

$$\sum_{ u \in Path } ( deg_u - used_u )$$

此处 $deg$ 表示入度。

接着，好丑对吧，化简一下。

设该路径 $Path$ 有 $k$ 个点，有总 $used$ 为 $2 + (k - 2) \cdot 2 = 2 \cdot (k - 1)$。

此处方便故设 $in_u = deg_u - 2$。

则总贡献为：

$$\begin{aligned} &\sum_{ u \in Path } deg_u - 2 \cdot (k - 1) \\ =&\sum_{ u \in Path }(in_u + 2) - 2k + 2 \\ =&\sum_{ u \in Path }in_u + 2 \end{aligned}$$

此处显然可以将问题转化为：

求出树上至少两个点的简单路径的最大点权和加二（$\sum_{ u \in Path }in_u + 2$）。

推出这里就发现类似 dp 了。

最后，考虑状态定义以及转移。

定义：$dp_u$ 表示在 $u$ 的子树内，从 $u$ 出发向下的 $\max \sum_{ u \in Path }$。

初始化：$dp_u = in_u$。

转移：已经处理完所有儿子的 $dp_v$ 时，我们分两种情况讨论（前提是有儿子）。

• 自己加一个最大的儿子。
• （有至少两个儿子的前提）两个子链加上自己的权值。

答案即 $\max ( \sum_{ u \in Path } dp_u )+ 2$。

---

:::success[$\textup{Code}$] 喵喵。

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 2e5 + 5;
struct star{
    int nxt, to;
}edge[MAXN * 2];
int head[MAXN], cnt;
void add( int u, int v ){
    edge[++ cnt] = { head[u], v };
    head[u] = cnt;
}

int N, in[MAXN], ans = -1e9, u, v;
int dp[MAXN];//dp[u]表示在u的子树中，从u出发向下的最大in路径和
void dfs( int u, int fa ){
    vector<int> ch;//->child 儿子的dp值
    for( int i = head[u]; i; i = edge[i].nxt ){
        int v = edge[i].to;
        if( v == fa ) continue;
        dfs( v, u );
        ch.emplace_back( dp[v] );//丢进来
    }
    dp[u] = in[u];//初始化 
    if( ch.empty() ) return;
    sort( ch.begin(), ch.end(), greater<int>() );
    ans = max( ans, in[u] + ch[0] );
    //第一个：u + 一个子节点
    if( ch.size() >= 2 ) ans = max( ans, in[u] + ch[0] + ch[1] );
    //第二个：子链1 + u + 子链2
    dp[u] = in[u] + max( 0, ch[0] );
    //更新 即返回从u向下的最大链和
}

int main(){
	// freopen( "parade.in", "r", stdin );
	// freopen( "parade.out", "w", stdout ); 
    cin >> N;
    for( int i = 1; i < N; i ++ ){
        cin >> u >> v;
        add( u, v ), add( v, u );
        in[u] ++, in[v] ++;
    }
    for( int i = 1; i <= N; i ++ ) in[i] -= 2;
    //预处理
    dfs( 1, 0 );
    cout << ans + 2;
    return 0;
}

:::

---

$\textup{Last}$

审核管理员辛苦了，如果您有什么看不懂、我太弱了所以讲错了的地方，请您在评论区指出或着喵喵喵，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗?

QWQ。

谢谢你看到这里~