题解：P12747 [POI 2016 R3] 巡游 Parade
Herocket
·
·
题解
题目大意
有 n 个路口和 (n-1) 条双向道路（也就是树），有一巡游队伍从任意路口出发，到另一路口，需要在途中的路口处，对未使用道路设置路障，求路障数量最大值。
思路
对于任意节点 u，经过它的路径无非两种。
-
\text child1$ $\rightarrow$ $u
-
\text child1$ $\rightarrow$ $u$ $\rightarrow$ $\text child2
用 f_{u,0} 表示经过 u 的路线 1 的最大值，用 f_{u,1} 表示经过 u 的路线 2 的最大值。
设节点 u 的孩子中，答案最大的是 v1，次大是 v2。对于路线 1 则有：
f_{u,0} = f_{v1,0}+\text deg_u-2
其中 \text deg_u 表示节点 u 的度。
这 -2 是怎么来的呢？因为把 v1 \rightarrow u 的路障都算了两遍，但本身这不应该算，因为它们是使用的。
同理对于路线 2 有：
f_{u,1} = f_{v1,0}+f_{v2,0}+\text deg_u-4
初始化就是 $f_{u,0} = f_{u,1} = \text deg_u$。但要**注意**，起点和终点不能是同一个点，记录答案时应记录**转移后**的最大值，而不是当前状态最大值，因为这个最大值有可能是 $\text deg_u$，这不应该成为答案。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int head[200005],deg[200005],vis[200005];
int f[200005][2];
int cnt,ans;
struct node
{
int to,nxt;
}a[400005]; // 无向边要开2倍
void add(int u,int v) // 链式前向星
{
a[++cnt].to = v;
a[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int u)
{
vis[u] = 1;
f[u][0] = f[u][1] = deg[u];
int m1 = 0,m2 = 0,cnt1 = 0; // m1、m2分别记录f[v][0]的最大值和次大值
for(int i = head[u];i;i = a[i].nxt)
{
int v = a[i].to;
if(vis[v] == 1) continue;
dfs(v);
cnt1++;
f[u][0] = max(f[u][0],f[v][0]+deg[u]-2);
if(m1 < f[v][0]){
m2 = m1;
m1 = f[v][0];
}
else if(f[v][0] > m2) m2 = f[v][0];
ans = max(ans,f[v][0]+deg[u]-2); // 记录最终答案时应记录转移
}
if(cnt1 > 1){ // 至少有两个孩子才能走路线2
f[u][1] = m1+m2+deg[u]-4;
ans = max(ans,f[u][1]);
}
}
int main()
{
int n;
scanf("%d",&n);
int u,v;
for(int i = 1;i < n;i++){
scanf("%d %d",&u,&v);
add(u,v),add(v,u);
deg[u]++,deg[v]++;
}
dfs(1);
cout << ans;
return 0;
}
```