题解 CF1338D 【Nested Rubber Bands】

· · 题解

考虑有三个环 a,b,c 按顺序嵌套在一起在什么时候合法：

  2. 不存在若干个顺次连接的环与 a,c 分别相交，但是与 b 不相交。

对于第一个限制，选出来的点是独立集即可。

对于第二个限制，与 a,c 相交的极小的“顺次连接的环”实际上由 a 到 c 路径上的所有点构成，因此只有当 b 到路径 (a,c) 的距离小于等于 1 的时候才合法。

所以对于合法序列 a_1,a_2,a_3,\dots a_k，必有 a_i 到路径 (a_1,a_k) 的距离小于等于 1，换言之，这些点一定是树上的一个导出“毛毛虫”的独立集。

那么剩下的就是一个很简单的树形 dp 了，复杂度为 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define V inline void
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2e5+1;
vector<int>e[N];
int n,ans,f[N],g[N];
V add_edge(int x,int y){e[x].push_back(y),e[y].push_back(x);}
V cmax(int&x,int y){if(x-y>>31)x=y;}
V dfs(int u,int fa=0){
    int d=e[u].size();
    for(int v:e[u])if(v!=fa){
        dfs(v,u);
        cmax(ans,max(f[u]+g[v]+1,g[u]+f[v]+d-2));
        cmax(f[u],g[v]),cmax(g[u],f[v]);
    }
    cmax(ans,++f[u]),cmax(ans,g[u]+=d-1-!!fa),cmax(f[u],g[u]);
}
int main(){
    scanf("%d",&n);
    for(int x,y;--n;add_edge(x,y))scanf("%d%d",&x,&y);
    dfs(1),cout<<ans;
    return 0;
}