题目

一棵树上有一个古籍，这个古籍可以影响到与它距离为 \(d\) 以内的点。现在给出被影响到的点，问古籍可能在多少个点上。

\(0\le m,d\le n\le 10^5\)。

分析

原问题不好做，把问题转化为求每个点距离最远的古籍的距离，最后统计有多少个符合要求的。

这是一个树形dp的经典问题，于是就在cf上WA了三次……

做法是分两次求出一个点距离子树中最远的点，以及子树外最远的点。

WA的原因是没有考虑好哪些点不存在下面和子树外的点，导致统计出现问题。以后这种题要把数组初始化为-1，每次转移都要判断一下。

代码

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

using namespace std;

int read() {

	int x=0,f=1;

	char c=getchar();

	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int maxn=1e5+1;

bool spe[maxn];

vector<int> g[maxn];

inline void add(int x,int y) {g[x].push_back(y);}

inline void Max(int &x,int y) {x=max(x,y);}

int down[maxn],up[maxn];

void Down(int x,int fa) {

	int &dw=down[x]=spe[x]?0:-1;

	for (int v:g[x]) if (v!=fa) {

		Down(v,x);

		if (spe[v]) Max(dw,1);

		if (~down[v]) Max(dw,down[v]+1);

	}

}

void Up(int x,int fa) {

	pair<int,int> fir(-1,0),sec(-1,0);

	for (int v:g[x]) if (v!=fa) {

		if (down[v]>fir.first) swap(fir,sec),fir=make_pair(down[v],v); else if (down[v]>sec.first) sec=make_pair(down[v],v);

	}

	for (int v:g[x]) if (v!=fa) {

		int &uv=up[v]=-1;

		if (v!=fir.second && ~fir.first) uv=fir.first+2; else if (~sec.first) uv=sec.first+2;

		if (spe[x]) Max(uv,1);

		if (~up[x]) Max(uv,up[x]+1);

		Up(v,x);

	}

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	int n=read(),m=read(),k=read();

	for (int i=1;i<=m;++i) spe[read()]=true;

	for (int i=1;i<n;++i) {

		int x=read(),y=read();

		add(x,y),add(y,x);

	}

	Down(1,1);

	up[1]=-1;

	Up(1,1);

	int ans=0;

	for (int i=1;i<=n;++i) ans+=(max(up[i],down[i])<=k);

	printf("%d\n",ans);

	return 0;

}

巴特西

CF337D-Book of Evil

题目

分析

代码

最新文章

热门文章