题目

一棵树上有一个古籍，这个古籍可以影响到与它距离为 \(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; }

转载于:https://www.cnblogs.com/owenyu/p/7142724.html