阔力梯的树_牛客博客

人都傻了

$dsu$ 倒是模板,被 $set$ 的操作搞晕了...

$s.lower\_bound(int)$ 返回一个大于等于查找元素的指针

$s.end()$ 是 $set$ 的末尾位置,但是最后一个元素在末尾位置的前面 $!!!$

当 $lower\_bound$ 返回 $s.end()$ 说明没找到这个元素

至于这里用 $set$ 也是有原因的,因为编号不重复,否则需要使用 $multiset$

回到这道题,维护每个点的结实度

显然想知道一个点的结实度必须要把所有子节点的编号排成一个序列计算

但是直接计算是 $O(n^2)$ 的

考虑到这个序列是可以合并的,答案也是小幅度修改,可以使用 $dsu$

使用 $set$ 来储存当前子树内的编号序列

加入一个编号时,直接 $lower\_bound$ 找到插入的前驱后继,累加权值

删除时同理

这样就变成模板了

插入时分四种情况来写

$set$ 内元素个数只有 $1$ 个

无前驱

无后继

有前驱和后继

删除同理

然后就直接套用 $dsu\_on\_tree$ 的模板

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+10;
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){ d[++cnt] = (edge){v,head[u]},head[u] = cnt; }
int n,m,son[maxn],siz[maxn],sum,SON,ans[maxn];
void dfs(int u)
{
    siz[u] = 1;
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        dfs(v);
        siz[u] += siz[v];
        if( siz[v]>siz[son[u]] )    son[u] = v;
    }
}
set<int>s;
set<int>::iterator it;
int pre(set<int>::iterator it)    { return *(--it); }
int nxt(set<int>::iterator it)    { return *(++it); }
void ADD(int u)
{
    if( !s.size() )    { s.insert(u); return; }
    it = s.lower_bound(u);//找到第一个大于等于的
    int pr = pre(it), nx = *it;
    if( it==s.begin() )    sum += (nx-u)*(nx-u);
    else if( it==s.end() )    sum += (u-pr)*(u-pr);
    else
    {
        sum -= (nx-pr)*(nx-pr);
        sum += (nx-u)*(nx-u)+(u-pr)*(u-pr);
    }
    s.insert(u);
}
void del(int u)
{
    if( s.size()==1 )    { s.erase(u); return; }
    it = s.lower_bound(u);
    int pr = pre(it),nx = nxt(it);
    if( it==s.begin() )    sum -= (nx-*it)*(nx-*it);
    else if( *it==pre(s.end()) )    sum -= (pr-*it)*(pr-*it);
    else
    {
        sum += (nx-pr)*(nx-pr);
        sum -= (nx-u)*(nx-u)+(u-pr)*(u-pr);
    }
    s.erase(u);
}
void cal(int u,int type)
{
    ( type?ADD(u):del(u) ); 
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v!=SON )    cal( v,type );
    }
}
void dsu(int u,int type)
{
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v!=son[u] )    dsu( v,0 );
    }
    if( son[u] )    dsu( son[u],1 ),SON = son[u];
    cal(u,1); ans[u] = sum; SON=0;
    if( !type )    cal(u,0);
}
signed main()
{
    cin >> n;
    for(int i=2;i<=n;i++)
    {
        int x; scanf("%lld",&x);
        add(x,i);
    }
    dfs(1); dsu(1,1);
    for(int i=1;i<=n;i++)    printf("%lld\n",ans[i] );
}