阔力梯的树_牛客博客

阔力梯的树

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

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

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

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

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

假设我们插入 $x$ ，数组最前面的值为 $y$ ，所以答案加上 $(x - y) ^ 2$ 。

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

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

这个时候 $x, y$ 不紧邻了，所以我们要对整体的答案减去 $(x - y) ^ 2$ ，因为 $x$ 与 $value$ 紧邻，所以答案加上 $(x - value) ^ 2$ ； $y$ 与 $value$ 紧邻，所以答案加上 $(y - value) ^ 2$ 。

最后我们把以上操作用一个 $set$ 来进行维护就好了，整体复杂度 $O(n \log n \log n)$ 。

#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;
}