[题解]P11294 [NOISG 2022 Qualification] Tree Cutting

P11294 [NOISG 2022 Qualification] Tree Cutting

删除一条边，会产生两棵树，此时最优就是将两树的直径端点连起来，答案为两树直径之和再\({}+1\)。

因此考虑枚举删除的边 \((u,v)\)，不妨令 \(u\) 为父节点。我们需要知道：

• 子树 \(v\) 的直径。
• 原树删除子树 \(v\) 后的直径。

前者只需要按正常的树形 DP，记录每个节点能向下延伸的最长、次长链（\(mx[u][0/1]\)）即可求得。

后者的答案相当于在下面三项中选两项：

• 删去子树 \(v\) 后，从 \(u\) 向下延伸的最长链。
• 删去子树 \(v\) 后，从 \(u\) 向下延伸的次长链。
• 从 \(u\) 向子树 \(u\) 外延伸的最长链。

第三项可以采用 \(2\) 次 DFS 的方法，一次从下往上，一次从上往下（即 P10962）。

前两项可以额外维护 \(u\) 能向下延伸的第 \(3\) 长链（\(mx[u][2]\)）。

• 若 \(mx[v][0]+1=mx[u][0]\)，则删除 \(v\) 后的最长链、次长链即为 \(mx[u][1],mx[u][2]\)。
• 若 \(mx[v][0]+1=mx[u][1]\)，则删除 \(v\) 后的最长链、次长链即为 \(mx[u][0],mx[u][2]\)。
• 其他情况，删除 \(v\) 后的最长链、次长链即为 \(mx[u][0],mx[u][1]\)。

时间复杂度 \(O(n)\)。

点击查看代码

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=3e5+5;
int n,mx[N][3],g[N],f[N],ans;//mx:子树内前k大的距离  g:子树内的直径  f:子树外最大的距离 
inline void merge(int a[3],int w){if(w>=a[0]) a[2]=a[1],a[1]=a[0],a[0]=w;else if(w>=a[1]) a[2]=a[1],a[1]=w;else if(w>=a[2]) a[2]=w;
}
vector<int> G[N];
inline void dfs1(int u,int fa){for(int i:G[u]){if(i^fa){dfs1(i,u);merge(mx[u],mx[i][0]+1);g[u]=max(g[u],g[i]);}}g[u]=max(g[u],mx[u][0]+mx[u][1]);
}
inline void dfs2(int u,int fa){for(int i:G[u]){if(i^fa){if(mx[i][0]+1==mx[u][0]) f[i]=max(f[u],mx[u][1])+1;else f[i]=max(f[u],mx[u][0])+1;dfs2(i,u);ans=max(ans,g[i]+1+(mx[i][0]+1==mx[u][0]?mx[u][1]+max(f[u],mx[u][2]):mx[i][0]+1==mx[u][1]?mx[u][0]+max(f[u],mx[u][2]):mx[u][0]+max(f[u],mx[u][1])));}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n;for(int i=1,u,v;i<n;i++){cin>>u>>v;G[u].eb(v),G[v].eb(u);}dfs1(1,0),dfs2(1,0);cout<<ans<<"\n";return 0;
}