一句话题意：给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于等于l的点有多少个。
我：似乎并不好做啊。。。看了题解后大雾。。。
sol：考虑树上差分，对于一个点，在他那个位置++，再找到最远的一个点使得该点与当前点的距离小于等于l，在找到的那个点的父亲处--，至于实现倍增好像可以轻松解决。
#include <cstdio> using namespace std; #define int long long const int N=200005; int n,up,fa[N][23],re[N],d[N]; signed main() { int i,j,tmp; scanf("%lld%lld",&n,&up); re[1]=1; fa[1][0]=0; for(i=2;i<=n;i++) { scanf("%lld%lld",&fa[i][0],&d[i]); d[i]=d[i]+d[fa[i][0]]; for(j=1;j<=19;j++)fa[i][j]=fa[fa[i][j-1]][j-1]; tmp=i; for(j=19;~j;j--)if(d[i]-d[fa[tmp][j]]<=up)tmp=fa[tmp][j];//找到那个点 re[fa[tmp][0]]--; re[i]++; }for(i=n;i>=2;i--)re[fa[i][0]]+=re[i]; for(i=1;i<=n;i++)printf("%lld\n",re[i]); }
洛谷P3066 [USACO12DEC]逃跑的BarnRunning Away From…
原文：https://www.cnblogs.com/gaojunonly1/p/9738663.html