CF739B Alyona and a tree

嘟嘟嘟

前缀和+倍增+树上差分

假设\(v\)是\(u\)子树中的一个点，那么\(u\)能控制\(v\)的条件是受\(v\)的权值的限制，而并非\(u\)。因此我们就能想到计算每一个点的贡献，即\(v\)有多少个祖先能控制它。这样就能想到暴力的做法：枚举每一个点\(i\)，向上爬直到两点间距离大于\(a_i\)为止。然后树上差分（准确说是链上差分）即可。至于两点间距离，采用前缀和相减。

但这样的复杂度能达到\(O(n^2)\)，因此我们可以用倍增优化一步步向上跳，达到\(O(nlogn)\)。

总结一下，先\(dfs\)一遍求出每一个点到根节点的距离和差分数组，复杂度\(O(nlogn)\)；然后对于每一个点倍增向上跳，并修改差分数组，复杂度也是\(O(nlogn)\)；最后\(O(n)\) \(dfs\)一遍求查差分组的树上前缀和。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 2e5 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n;

ll a[maxn];

struct Edge

{

  int nxt, to, w;

}e[maxn];

int head[maxn], ecnt = -1;

void addEdge(int x, int y, int w)

{

  e[++ecnt] = (Edge){head[x], y, w};

  head[x] = ecnt;

}

int fa[21][maxn];

ll dis[maxn];

void dfs(int now)

{

  for(int i = 1; i <= 20; ++i)

    fa[i][now] = fa[i - 1][fa[i - 1][now]];

  for(int i = head[now], v; i != -1; i = e[i].nxt)

    {

      v = e[i].to;

      fa[0][v] = now;

      dis[v] = dis[now] + e[i].w;

      dfs(v);

    }

}

int dif[maxn];

void solve(int now)

{

  int x = now;

  for(int i = 20; i >= 0; --i)

      if(fa[i][x] && dis[now] - dis[fa[i][x]] <= a[now]) x = fa[i][x];

  if(x != 1) dif[fa[0][x]]--;

  if(now != 1) dif[fa[0][now]]++;

}

void dfs2(int now)

{

  for(int i = head[now], v; i != -1; i = e[i].nxt)

    {

      v = e[i].to;

      dfs2(v);

      dif[now] += dif[v];

    }

}

int main()

{

  Mem(head, -1);

  n = read();

  for(int i = 1; i <= n; ++i) a[i] = read();

  for(int i = 2; i <= n; ++i)

    {

      int x = read(), w = read();

      addEdge(x, i, w);

    }

  dfs(1);

  for(int i = 1; i <= n; ++i) solve(i);

  dfs2(1);

  for(int i = 1; i <= n; ++i) write(dif[i]), space; enter;

  return 0;

}