[BalticOI 2017] Cat in a tree

神仙美少女 Tweetuzki 学姐用了长剖+线段树，私以为长剖可以做到线性。

简要题意

给定 \(n\) 个点的树，点集 \(S\) 合法当且仅当 \(\forall u,v\in S, dis(u,v)\ge k\)。求 \(\max |S|\)。
\(n \le 2\times 10^5\)。

题解

记 \(f_{u,i}\) 表示以 \(u\) 为根的子树中，选择的深度最浅的点深度大于等于 \(i\) 的最大点集大小。此处深度针对这一子树而言。转移考虑加入一棵子树，方程比较简单：更新 \(f_{u,j}\) 时，记 \(t = \max(j,k-j)\)（分别保证状态的合法性和答案的合法性），\(f_{u,j}\leftarrow \max(f_{u,j}+f_{v,t-1}, f_{u,t}+f_{v,j-1})\)，最后做一遍后缀 \(\max\) 即可。

注意到当 \(j \gt dep_u\) 时，\(f_{u,j}=0\)。所以转移时只需要枚举到 \(dep_v\) 即可。这启发我们使用长剖优化。

代码

注意边界细节。

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAXN = 200010;

int n, K;

struct edge{

	int ne, to;

	edge(int N=0,int T=0):ne(N),to(T){}

}e[MAXN<<1];

int fir[MAXN], num = 0;

inline void join(int a, int b)

{

	e[++num] = edge(fir[a], b);

	fir[a] = num;

}

int buf[MAXN], *f[MAXN], *now = buf, dep[MAXN], son[MAXN], fa[MAXN];

void predfs(int u, int pa)

{

	fa[u] = pa;

	for(int i=fir[u],v;i;i=e[i].ne) if((v = e[i].to) != pa)

	{

		predfs(v, u);

		dep[u] = max(dep[u], dep[v]+1);

		if(dep[son[u]] < dep[v]) son[u] = v;

	}

	dep[u] = dep[son[u]] + 1;

}

void dfs(int u)

{

	f[u][0] = 1;

	if(son[u])

	{

		f[son[u]] = f[u] + 1;

		dfs(son[u]);

		if(K-1 < dep[son[u]]) f[u][0] += f[son[u]][K-1];

		f[u][0] = max(f[u][1], f[u][0]);

	}

	for(int i=fir[u],v;i;i=e[i].ne) if((v=e[i].to) != fa[u] && v != son[u])

	{

		f[v] = now; now += dep[v];

		dfs(v);

		for(int j=0;j<=dep[v];j++)

		{

			int k = max(j, K-j);

			f[u][j] = max(((k) ? (j<dep[u]?f[u][j]:0) + (k<=dep[v]?f[v][k-1]:0) : 0), (j ? (k<dep[u]?f[u][k]:0) + f[v][j-1] : 0));

		}

		for(int j=dep[v];~j;j--) f[u][j] = max(f[u][j], j==dep[u]-1?0:f[u][j+1]);

	}

}

int main()

{

	scanf("%d%d",&n,&K);

	for(int i=2,x;i<=n;i++)

	{

		scanf("%d",&x);

		join(i, ++x);

		join(x, i);

	}

	predfs(1, 0);

	f[1] = now; now += dep[1];

	dfs(1);

	printf("%d\n",f[1][0]);

	return 0;

}

巴特西

[BalticOI 2017] Cat in a tree

[BalticOI 2017] Cat in a tree

简要题意

题解

代码

最新文章

热门文章