阔力梯的树 | dsu on a tree

emmm..

题意是计算每颗子树下，标号从小到大排列后，相邻项差值的平方和

涉及到静态子数问题， $dsu\ on\ a\ tree$ 就是经典解决方法了

$dsu\ on\ a\ tree$ 维护了静态子数的信息，所以只需要处理新加入的权值与当前权值的关系就好了

记得今年牛客2020多校有个三角形的加入边与删除边，维护最小差值的，与这个思路类似

首先把权值全部放入一个集合 $set$ 中，那么对于新加入的一个 $a_i$ ，它只会影响到 $a_i,a_{i+1},a_{i-1}$

所以显然，用set考虑新来的元素在set中的三种位置，就可以处理权值的大小变化

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e5+700;
const ll mod= 1e9+7;
const double eps = 1e-8;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
vector<int>v[maxn];
set<ll>s;
int sz[maxn],son[maxn];
ll res[maxn];
void dfs(int u){
    sz[u] = 1;
    for(int e:v[u]){
        dfs(e);
        sz[u] += sz[e];
        if(sz[son[u]] < sz[e]) son[u] = e;
    }
}
ll ans = 0;
ll gg(ll x){
    return x*x;
}
void add(ll x){
    if(!s.size()){
        s.insert(x);
        return;
    }
    auto u = s.lower_bound(x);
    if(u == s.begin()){
        ans = ans + gg(*u-x)*1ll;
    }
    else if(u == s.end()){
        u = prev(u),ans = ans + gg(*u-x)*1ll;
    }
    else{
        ll xx = *prev(u),y = *u;
        ans -= gg(xx-y)*1ll;
        ans += gg(xx-x)*1ll;
        ans += gg(y-x)*1ll;
    }
    s.insert(x);
}
void del(ll x){
    if(s.size() == 1){
        s.erase(x);
        return;
    }
    auto u = s.lower_bound(x);
    if(u == s.begin()) ans = ans - gg(x-(*next(u)))*1ll;
    else if(u == prev(s.end())) ans = ans - gg(x - (*prev(u)))*1ll;
    else{
        ll xx = *prev(u), y = *next(u);
        ans -= gg(xx-x)*1ll;
        ans -= gg(y-x)*1ll;
        ans += gg(xx-y)*1ll;
    } 
    s.erase(x);
    return;
}

void cal(int u,int f){
    if(f) add(u);
    else del(u);
    for(int e:v[u]) cal(e,f);
}

void _d(int u,int del){

    for(int e:v[u]){
        if(son[u] == e) continue;
        _d(e,1);
    }
    if(son[u]) _d(son[u],0);
    add(u);
    for(int e:v[u]){
        if(e == son[u]) continue;
        cal(e,1);
    }
    res[u] = ans;
    if(del) cal(u,0);
}


int main(){
    read(n);
    for(int i=2;i<=n;i++){
        int x;read(x);
        v[x].push_back(i);
    }
    dfs(1);
    _d(1,0);
    for(int i=1;i<=n;i++) printf("%lld\n",res[i]);
    return 0;
}
/***
***/