P10421

HasNoName · 2025-08-26 16:57:51 · 题解

思路

考虑点分治。

可以吧题目要计算的答案写成 \sum\limits_{i=1}^n{\sum\limits_{j=i+1}^{n}{dis(i,j)\cdot[dis(i,j) \le R]}}-\sum\limits_{i=1}^n{\sum\limits_{j=i+1}^{n}{dis(i,j)\cdot[dis(i,j)<L]}}。

然后就是板子了。

可以对于每一个点计算出它的答案（先不考虑在两条路径在同一棵子树内的情况），然后再对它的每个子树减去在同一个子树内的情况。

具体的，计算一颗子树内的答案（包括重复）时，可以先把子树内每个可能取到的从当前子树的根到一个子树内节点的距离存下来，然后在排序，通过两边双指针得到答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
typedef long long ll;
struct T
{
    int ne,to;
}e[2*N];
int he[N],idx,n,dw,up,vis[N],sz[N],f[N],tot,d[N];
ll c[N],top,p[N],s[N],ans;
void add(int x,int y)
{
    e[++idx].ne=he[x];
    e[idx].to=y;
    he[x]=idx;
}
int getwc(int x,int fa)//得到重心
{
    f[x]=0;sz[x]=1;int t=0;
    for(int i=he[x];i;i=e[i].ne)
    {
        int y=e[i].to;
        if(y==fa||vis[y])continue;
        int c=getwc(y,x);
        sz[x]+=sz[y];
        f[x]=max(f[x],sz[y]);
        if(f[c]<f[t])t=c;
    }
    f[x]=max(f[x],tot-sz[x]);
    if(f[t]>f[x])t=x;
    return t;
}
void dfs(int x,int fa)//计算距离
{
    if(d[x]>up)return;
    c[++top]=d[x];
    for(int i=he[x];i;i=e[i].ne)
    {
        int y=e[i].to;
        if(y==fa||vis[y])continue;
        d[y]=d[x]+1;
        dfs(y,x);
    }
}
ll get()//计算答案
{
    c[++top]=0;
    sort(c+1,c+top+1);
    for(int i=1;i<=top;i++)s[i]=s[i-1]+c[i];
    int l=1;ll sum=0;
    for(int r=top;r>=1;r--)//双指针
    {
        while(l<=r&&c[r]+c[l]<=up)l++;
        l--;
        sum+=s[l]+c[r]*l;
    }
    l=1;
    for(int r=top;r>=1;r--)
    {
        while(l<=r&&c[r]+c[l]<dw)l++;
        if(l>0)l--;
        sum-=s[l]+c[r]*l;
    }
    return sum;
}
void calc(int x)
{
    top=0;d[x]=0;
    dfs(x,0);
    ans+=get();
    for(int i=he[x];i;i=e[i].ne)
    {
        int y=e[i].to;
        if(vis[y])continue;
        top=0;d[y]=1;
        dfs(y,0);
        ans-=get();
    }
}
void run(int x)
{
    vis[x]=1;
    calc(x);
    for(int i=he[x];i;i=e[i].ne)
    {
        int y=e[i].to;
        if(vis[y])continue;
        tot=sz[y];
        run(getwc(y,0));
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>dw>>up;
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        add(x,i);
        add(i,x);
    }
    f[0]=1e9;tot=n;
    run(getwc(1,0));//点分治
    cout<<ans<<'\n';
    return 0;
}