CF740D Alyona and a tree(树上差分+二分)

原题地址:https://codeforces.com/contest/740/problem/D

题意:给一棵树,$v$节点被$u$节点控制当且仅当$v$时$u$子树中的点,并且$a[v]>=dis(u,v)$,其中$a[v]$是$v$节点的点权,$dis(u,v)$是$u$节点到$v$节点的边权和.,求每个节点可以控制的节点数数量.

思路:我们可以考虑每一个节点对其祖先的贡献,因为$a[v]>=dis(u,v)$,对于一个固定的点v来说,a[v]是固定的,随着树的深度减少,dis(u,v)在增加,存在单调性,因此我们可以二分出第一个不满足条件的祖先节点,那么在这个祖先节点之上的点,全都是不能控制v节点的. 因此我们将$a[v]>=dis(u,v)$转换为$a[v]>=dep[v]-dep[u]$,dep表示从根节点到某一节点的距离,$dep[u]>=dep[v]-a[v]$,因为$dep$随着树的深度的增加,是一直在增加的,二分第一个位置即可. 最后,我们可以用差分的方法快速计算每一个的答案.

#include <bits/stdc++.h> #define eps 1e-8 #define INF 0x3f3f3f3f #define PI acos(-1) #define lson l,mid,rt<<1 #define rson mid+1,r,(rt<<1)+1 #define CLR(x,y) memset((x),y,sizeof(x)) #define fuck(x) cerr << #x << "=" << x << endl using namespace std; typedef long long ll; typedef unsigned long long ull; const int seed = 131; const int maxn = 2e5 + 5; const int mod = 1e9 + 7; struct node { int v, w, nxt; } e[maxn * 2]; int tot, head[maxn]; void add_edge(int u, int v, int w) { e[tot].v = v; e[tot].w = w; e[tot].nxt = head[u]; head[u] = tot++; } struct No { int id; ll val; bool operator < (const No &a)const { return val < a.val; } No() {} No(int id, ll val): id(id), val(val) {} }; int n, a[maxn], ans[maxn]; //ans即差分数组,求完前缀和就是答案. ll dep[maxn]; vector<No>vec; void dfs(int u, int fa) {//每次计算节点u对其祖先的贡献 ll tmp = dep[u] - a[u]; //求最近的大于tmp的点 int pos = lower_bound(vec.begin(), vec.end(), No(0, tmp)) - vec.begin(); ans[fa]++;//u节点的父节点开始产生贡献,直到pos为止,用差分数组解决这个区间问题 if (pos > 0)ans[vec[pos - 1].id]--;//差分前面的点减1 vec.push_back(No(u, dep[u])); for (int i = head[u]; ~i; i = e[i].nxt) { int v = e[i].v; int w = e[i].w; if (v == fa) continue; dep[v] = dep[u] + w; dfs(v, u); ans[u] += ans[v]; } vec.pop_back(); } int main() { CLR(head, -1); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= n - 1; i++) { int p, w; scanf("%d%d", &p, &w); add_edge(i + 1, p, w); add_edge(p, i + 1, w); } dfs(1, 0); for (int i = 1; i <= n; i++) { printf("%d ", ans[i]); } return 0; }