pkusc时候做的题,现在发上来。
每个节点维护一个大根堆,维护从根节点到当前节点以及当前节点的子节点的路径长度(即深度)。
如果当前节点的堆的堆顶 - 当前节点的深度 大于L,那么删除堆顶,直到满足条件为止。
那么堆的size就是当前节点的答案。
当一个节点处理完毕后,把当前节点的堆与当前节点的父亲的堆合并,就可以了。
当一个节点的儿子都处理完后,那么就可以处理这个节点了,所以用类似拓扑序的思想,用一个队列搞。
可并堆用的左偏树。
/* Forgive me Not */ #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef long long LL; const int maxn = 200005; int n, pre[maxn], size[maxn], ans[maxn], du[maxn], son[maxn][2], root[maxn]; LL L, w[maxn]; queue<int> q; int dis[maxn]; inline void pushup(int x) { size[x] = size[son[x][0]] + size[son[x][1]] + 1; } inline int merge(int x, int y) { if(!x || !y) return x + y; if(w[x] < w[y]) swap(x, y); son[x][1] = merge(son[x][1], y); pushup(x); if(dis[son[x][0]] < dis[son[x][1]]) swap(son[x][0], son[x][1]); dis[x] = dis[son[x][1]] + 1; return x; } int main() { scanf("%d%lld", &n, &L); size[1] = 1; root[1] = 1; du[0] = -1; for(int i = 2; i <= n; i++) { scanf("%d%lld", &pre[i], &w[i]); w[i] += w[pre[i]]; size[i] = 1; root[i] = i; du[pre[i]]++; } for(int i = 1; i <= n; i++) if(!du[i]) q.push(i); while(!q.empty()) { int u = q.front(); q.pop(); for(; w[root[u]] - w[u] > L; root[u] = merge(son[root[u]][0], son[root[u]][1])); ans[u] = size[root[u]]; root[pre[u]] = merge(root[pre[u]], root[u]); du[pre[u]]--; if(!du[pre[u]]) q.push(pre[u]); } for(int i = 1; i <= n; i++) printf("%d\n", ans[i]); return 0; }