Parade

就是求树上，使得与路径相邻但是不在路径上的边的数量最大化的路径。

可以把路径分成两类，一是一直向根的方向走的路径，二是先往上走，然后又往下走的。按这个分类，用树上DP来求：

dp $[i][0]$ : 以 $i$ 为上端点单调往上走的路径的相邻边数最大值。
dp $[i][1]$ : 以 $i$ 为最高点（就是两端点都在 $i$ 子树中）的路径的相邻边数最大值。

可以看到（ $D_i$ 是节点 $i$ 的度）：

$\text{dp}[i][0] = \max_{u \in C}(\text{dp}[u][0], D_u) + D_i - 2$
$\text{dp}[i][1] = \max_{u,v \in C, u \neq v}(\max(\text{dp}[u][0], D_u) + \max(\text{dp}[v][0], D_v)) + D_i - 4$

然后对所有点求最大值就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;      // 2e5
vector<int> adj[200005];
int dp[200005][2];
 
bool isLeaf(int s) {
    return s != 0 && adj[s].size() == 1;
}
 
void dfs(int s, int e) {
    int outdeg = adj[s].size();
    int first = 0, second = 0;
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs(u, s);
        int v = max(dp[u][0], (int)adj[u].size());
        dp[s][0] = max(dp[s][0], v + outdeg - 2);
        if (v >= first) {
            second = first;
            first = v;
        } else second = max(second, v);
    }
    if (s == 0 && outdeg == 2 || outdeg >= 3)
        dp[s][1] = first + second - 2 + (outdeg - 2);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0, -1);
    int ans = 0;
    for (int i = 0; i < n; i++)
        if (i == 0 || adj[i].size() > 1)   // non-leaf
            ans = max(ans, max(dp[i][0], dp[i][1]));
    printf("%d", ans);
 
    return 0;
}