题目大意：给定一棵带点权的有根树，同时给定L,R，要求找M条链，每条链满足以下条件的情况下，要求所有链权和最大：
1、两两不相同（可以包含/相交等）
2、节点数在[L,R]间
3、其中一个端点的深度必须是整条链所有点深度的最小值（原谅我实在不会表达……）（形象地说，就是直上直下）
感觉和NOI某原题什么钢琴有点像
当一条链的下端点确定时，上端点的选择范围就是一条链，也就是说，我们可以求出每个点到根的点权和val[u]存入主席树，这样就可以求 以指定点为下端点 权第k大的链了。
用堆来维护 所有下端点当前权最大的链，每取出一个当前最大值，假设它是其下端点权第k大的链，就在主席树里找这个下端点权第k+1大的链
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long
#define N 500005
#define M 500005
#define INF (1e9) using namespace std;
inline int read(){
int ret=0;char ch=getchar();
bool flag=0;
while (ch<'0'||ch>'9'){
flag=ch=='-';
ch=getchar();
}
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return flag?-ret:ret;
} int n;
int fa[N],f[N][22],fl[N],fr[N],deep[N];
int a[N],val[N];
int need,L,R;
int root[N]; void init(){
n=read()+1;fa[2]=read()+1;
for (int i=3;i<=n;++i) fa[i]=read()+1;
for (int i=2;i<=n;++i) a[i]=read();
fa[1]=a[1]=0;
need=read();L=read();R=read()+1;//interval->[L,R)
} struct SegmentTree{
struct STnode{
int sum,ls,rs;
} t[N*33];
int size;
void clear(){size=t[0].sum=t[0].ls=t[0].rs=0;}
void modify(int &x,int L,int R,int pos){
t[++size]=t[x];
x=size;
++t[x].sum;
if (L==R) return;
int mid=(L+R)/2;
if (L+R<0) --mid;
if (pos<=mid) modify(t[x].ls,L,mid,pos);
else modify(t[x].rs,mid+1,R,pos);
}
int qmink(int x,int y,int L,int R,int k){
if (L==R) return L;
int tmp=t[t[x].ls].sum-t[t[y].ls].sum,mid=(L+R)/2;
if (L+R<0) --mid;
if (k<=tmp) return qmink(t[x].ls,t[y].ls,L,mid,k);
else return qmink(t[x].rs,t[y].rs,mid+1,R,k-tmp);
}
} st; void precompute(){
val[0]=a[0]=deep[0]=fa[0]=0;
for (int i=1;i<=n;++i){
val[i]=val[fa[i]]+a[i];
deep[i]=deep[fa[i]]+1;
f[i][0]=fa[i];
}
memset(f[0],0,sizeof(f[0]));
for (int k=1;k<=20;++k)
for (int i=1;i<=n;++i)
f[i][k]=f[f[i][k-1]][k-1]; st.clear();root[0]=0;
for (int i=1;i<=n;++i){
fl[i]=fr[i]=i;
for (int k=0;k<=20;++k){
if ((L&(1<<k))>0) fl[i]=f[fl[i]][k];
if ((R&(1<<k))>0) fr[i]=f[fr[i]][k];
} st.modify(root[i]=root[fa[i]],-INF,INF,val[i]);
}
} struct HeapNode{
int pos,value,k;
HeapNode(){}
HeapNode(int _pos,int _value,int _k):pos(_pos),value(_value),k(_k){}
};
inline bool operator <(const HeapNode &u,const HeapNode &v){
return u.value<v.value;
}
priority_queue<HeapNode> h; void work(){
while (!h.empty()) h.pop();
for (int i=1;i<=n;++i)
if (deep[fl[i]]-deep[fr[i]])
h.push(HeapNode(i,val[i]-st.qmink(root[fl[i]],root[fr[i]],-INF,INF,1),1));
ll ans=0;
while (need--){
HeapNode now=h.top();
h.pop();
ans+=(ll)now.value;
int u=fl[now.pos],v=fr[now.pos];
if (deep[u]-deep[v]>now.k)
h.push(HeapNode(now.pos,val[now.pos]-st.qmink(root[u],root[v],-INF,INF,now.k+1),now.k+1));
}
printf("%lld\n",ans);
} int main(){
init();
precompute();
work();
return 0;
}