题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3011
STL大法好！
最开始觉得，用一个set好像就可以，但是稍微仔细想想就错的很离谱
我们需要dfs算出每个点的深度deep，然后对每个点维护一个大根堆，存它子树的deep，当top-deep[now]>L时，就pop掉堆顶
但是显然还需要向上合并，暴力并不可行，但是懒得写可并堆，就用了pb_ds
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<bits/stdc++.h> #include<ext/pb_ds/priority_queue.hpp> #define MAXN 200020 typedef long long ll; using namespace std; using namespace __gnu_pbds; inline ll rd(){ ll x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,ans[MAXN],fa[MAXN]; ll len[MAXN],deep[MAXN],m; vector<int>v[MAXN]; __gnu_pbds::priority_queue<ll>pq[MAXN]; void dfs(int x){ deep[x]=deep[fa[x]]+len[x]; for(int i=0; i<v[x].size(); i++)dfs(v[x][i]); while(!pq[x].empty() && pq[x].top()-deep[x]>m)pq[x].pop(); ans[x]=pq[x].size()+1; pq[fa[x]].join(pq[x]); pq[fa[x]].push(deep[x]); } int main(){ n=rd(),m=rd(); for(int i=2; i<=n; i++){ int x=rd(); ll y=rd(); v[x].push_back(i); len[i]=y,fa[i]=x; } dfs(1); for(int i=1; i<=n; i++)printf("%d\n",ans[i]); return 0; } |
