题号 NC201890
名称 阔力梯的树
来源 2020 CCPC Wannafly Winter Camp Day2 Div.1&2
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

阔力梯的树

一般树上问题的求解有三种方法：点分治、树链剖分、。

这道题目中，结实程度是在子树上的定义，所以容易想到，所以我们可以考虑如何通过来维护子树信息。

如果使用来考虑求解，我们必然要涉及到点权插入到一个升序的数组中，考虑插入这个点之后，整体结实程度如何变化，大致分为一下几步。

一、第一个权值插入，这个时候对整体结实程度是没有任何影响的。

二、权值插入在数组的最前面，这个时候整体结实程度的改变也就是当前这个值与数组最前面的元素之间的关系

假设我们插入，数组最前面的值为，所以答案加上。

三、权值插入在数组的最后面，同情况二，结实程度的改变只与当前值与数组末尾值有关，假设我们插入，数组末尾的值为，这个时候答案也是加上。

四、权值在中间插入，这种情况就稍微复杂一点点了，假设其插入位置的前驱值为，其插入位置后驱值为，插入值为。

这个时候不紧邻了，所以我们要对整体的答案减去，因为与紧邻，所以答案加上；与紧邻，所以答案加上。

最后我们把以上操作用一个来进行维护就好了，整体复杂度。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int head[N], to[N << 1], nex[N << 1], cnt = 1;

int sz[N], l[N], r[N], son[N], rk[N], n, tot, now_son;

void add(int x, int y) {
  to[cnt] = y;
  nex[cnt] = head[x];
  head[x] = cnt++;
}

void dfs(int rt, int fa) {
  rk[++tot] = rt;
  sz[rt] = 1, l[rt] = tot;
  for(int i = head[rt]; i; i = nex[i]) {
    if(to[i] == fa) {
      continue;
    }
    dfs(to[i], rt);
    if(!son[rt] || sz[to[i]] > sz[son[rt]]) {
      son[rt] = to[i];
    }
    sz[rt] += sz[to[i]];
  }
  r[rt] = tot;
}

set<int> st;

ll ans[N], sum;

void add(int x) {
  auto it = st.lower_bound(x);
  if(st.empty()) {
    st.insert(x);
    return;
  }
  if(it == st.end()) {
    --it;
    sum += 1ll * (x - *it) * (x - *it);
    st.insert(x);
    return;
  }
  if(it == st.begin()) {
    sum += 1ll * (*it - x) * (*it - x);
    st.insert(x);
    return;
  }
  int vr = *it, vl = *--it;
  sum += 1ll * (vr - x) * (vr - x) + 1ll * (x - vl) * (x - vl) - 1ll * (vr - vl) * (vr - vl);
  st.insert(x);
}

void dsu(int rt, int fa, bool keep) {
  for(int i = head[rt]; i; i = nex[i]) {
    if(to[i] == fa || to[i] == son[rt]) {
      continue;
    }
    dsu(to[i], rt, 0);
  }
  if(son[rt]) {
    dsu(son[rt], rt, 1);
  }
  for(int i = head[rt]; i; i = nex[i]) {
    if(to[i] == fa || to[i] == son[rt]) {
      continue;
    }
    for(int j = l[to[i]]; j <= r[to[i]]; j++) {
      add(rk[j]);
    }
  }
  add(rt);
  ans[rt] = sum;
  if(!keep) {
    sum = 0;
    st.clear();
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d", &n);
  for(int i = 2; i <= n; i++) {    
    int x;
    scanf("%d", &x);
    add(x, i);
    add(i, x);
  }
  dfs(1, 0);
  dsu(1, 0, 1);
  for(int i = 1; i <= n; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
} 

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目1月6日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴