怎么感觉这是个玄学算法
基础思路
对于一个以 \(u\) 为根节点的子树内，其所有路径可以分为两类：
1.经过 \(u\) 点的
2.不经过 \(u\) 点的
所以我们可以进行分治，进行深搜，对于每一个点处理经过自己的，然后去深搜解决其子节点
但是这样的算法对于链状的树就炸了，处理自己的 \(O(n)\) ， 深搜 \(O(n)\) ，时间复杂度会退化到 \(O(n^2)\)
所以不妨每次找到重心作为根节点，然后再处理
然后我们就得到了淀粉质
例题
这里
考虑对于每个点，应该怎么计算经过它的合法路径长度
我们可以跑出字数内每个点到当前节点的距离，排序后扫一遍双指针，扫出所有距离和在给定区间内的点对
（在代码中，利用了容斥原理，\(counter\) 函数表示所有距离不小于 \(lim\) 的点对）
但是这样会发现同一个子节点的子树内的点也会被计算进去，所以提前减掉即可
代码
#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int inf=2e9+1;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
int head[maxn],nxt[maxn<<1],e[maxn<<1];
int mp_cnt;
void init_mp(){memset(head,-1,sizeof(head));mp_cnt=-1;
}
void add_edge(int u,int v){e[++mp_cnt]=v;nxt[mp_cnt]=head[u];head[u]=mp_cnt;
}
int t[maxn];
int n,l,r;
int vis[maxn],s[maxn];
int rt,rti,tot;
LL ans=0;
void bsort(vector<int>& v){//桶排int mx=0;for(int i=0;i<(int)v.size();i++){++t[v[i]];mx=max(mx,v[i]);}v.clear();for(int i=0;i<=mx;i++){while(t[i]){--t[i];v.push_back(i);}}
}
void get_rt(int u,int fa){//寻找子树重心int p=0;s[u]=1;for(int i=head[u];~i;i=nxt[i]){int v=e[i];if(v==fa||vis[v]) continue;get_rt(v,u);s[u]+=s[v];p=max(p,s[v]);}p=max(p,tot-s[u]);if(p<=rti) rt=u,rti=p;
}
vector<int> v1,v2;
void get_dis(int u,int fa,int d){//获取子树内所有距离v1.push_back(d),v2.push_back(d);for(int i=head[u];~i;i=nxt[i]){int v=e[i];if(v==fa||vis[v]) continue;get_dis(v,u,d+1);}
}
LL counter(vector<int>& v,int lim){//双指针LL p=0,sum=0;int r=(int)v.size()-1;for(int i=0;i<(int)v.size();i++) sum+=v[i];for(int i=0;i<(int)v.size();i++){sum-=v[i];while(r>=0&&v[i]+v[r]>lim) sum-=v[r--];if(r<i) break;p+=sum+1ll*(r-i)*v[i];}return p;
}
void work(int u){//计算答案v1.clear();v1.push_back(0);for(int i=head[u];~i;i=nxt[i]){int v=e[i];if(vis[v]) continue;v2.clear();get_dis(v,u,1);bsort(v2);ans-=counter(v2,r)-counter(v2,l-1);}bsort(v1);ans+=counter(v1,r)-counter(v1,l-1);
}
void dfs(int u){vis[u]=1,work(u);for(int i=head[u];~i;i=nxt[i]){int v=e[i];if(vis[v]) continue;rti=inf,tot=s[v];get_rt(v,u);dfs(rt);}
}
int main(){read(n),read(l),read(r);int u;init_mp();for(int i=2;i<=n;i++){read(u);add_edge(u,i),add_edge(i,u);}tot=n,rti=inf;get_rt(1,1);dfs(rt);printf("%lld",ans);return 0;
}
//^o^
你可能会发现在求重心时的子树大小并不是正确的，因为其根节点是不同的
但是这并不影响正确性与时间复杂度，详见这里
所以你会发现，这里不能使用 \(oi\;wiki\) 中这种方法来判断重心
由于使用了桶排，这段代码的时间复杂度为 \(O(n\;log\;n)\)