萌新刚学 1ms，求调小清新数据结构题

//when you use vector or deque,pay attention to the size of it.
//by OldDriverTree
#include<bits/stdc++.h>
//#include<atcoder/all>
//#include<bits/extc++.h>
#define range(vec) vec.begin(),vec.end()
#define siz(vec) (int)vec.size()
#define tup array<int,3>
#define P pair<int,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
//using namespace atcoder;
//using namespace __gnu_pbds;
//using mint=modint998244353;
const int N=1e5+1,M=501;
int fa[N],Fa[N],dep[N],near[N];
int n,m,B,t,tot,id[N],di[M],Id[N];
int cnt,dfn[N],st[17][N],p[N][2];
vector<vector<int> > h[M][2][2];
vector<int> a,b[N],g[N],dis[N];
vector<P> G[M],f[M][2][2];
P F[M],H[M];

int read() {
    int x=0; bool _=true; char c=0;
    while (!isdigit(c) ) _&=(c!='-'),c=getchar();
    while (isdigit(c) ) x=x*10+(c&15),c=getchar();
    return _?x:-x;
}
namespace cluster
{
    vector<int> p,stk;
    int siz[N],cur[N],awa[N];
    void build(int x,int y) {
        Fa[y]=x,near[x]=x,tot++,di[tot]=y,b[tot].swap(p);
        for (int o=y;o^x;o=fa[o]) near[o]=o;
        for (int o:b[y]) id[o]=tot,!near[o]&&(near[o]=near[fa[o] ]);
        if (!t) t=tot,b[tot].insert(b[tot].begin(),1),id[1]=tot;
    }
    void dfs(int u)
    {
        st[0][dfn[u]=++cnt]=fa[u];
        siz[u]=1,cur[u]=stk.size(); int cnt=0;
        for (int v:g[u]) {
            stk.push_back(v),fa[v]=u,dep[v]=dep[u]+1,dfs(v);
            siz[u]+=siz[v]; if (awa[v]) awa[u]=awa[v],cnt++;
        }
        if (siz[u]>B||cnt>1||u==1)
        {
            siz[u]=1,awa[u]=u,a.push_back(u),cnt=0;
            for (int i=0,now=cur[u],o=0;i<=g[u].size();i++)
            {
                int v=i<g[u].size()?g[u][i]:0;
                if (cnt+siz[v]>B||(o&&awa[v])||!v) {
                    int r=v?cur[v]-1:stk.size();
                    while (now<r) p.push_back(stk[now++]);
                    build(u,o?o:p.back() ),o=cnt=0;
                }
                cnt+=siz[v];
                if (awa[v]) o=awa[v];
            }
            stk.resize(cur[u]);
        }
    }
}
void dfs(int u,int fa,int len,int rt) {
    dis[rt][u^Fa[di[id[rt] ] ]?Id[u]:b[id[rt] ].size()]=len;
    for (int v:g[u]) if (v^fa) dfs(v,u,len+1,rt);
}
int LCA(int x,int y) {
    if (x==y) return x; x=dfn[x],y=dfn[y];
    if (x>y) swap(x,y); int k=__lg(y-x);
    x=st[k][x+1],y=st[k][y-(1<<k)+1];
    return dep[x]<dep[y]?x:y;
}
int Dis(int x,int y) { return dep[x]+dep[y]-2*dep[LCA(x,y)]; }
P operator +(P x,int y) { return {x.first,x.second+y*x.first}; }
P operator +(P x,P y) { return {x.first+y.first,x.second+y.second}; }
P operator -(P x,P y) { return {x.first-y.first,x.second-y.second}; }
int operator *(P x,P y) { return x.first*y.second+x.second*y.first; }
P get(int x,int y,int z) {
    if (z==INT_MAX) return {0,0};
    else if (z>=0) return f[x][y][0][min(z,siz(f[x][y][0])-1)];
    else return f[x][y][1][min(-z-1,siz(f[x][y][1])-1)];
}
int Get(int x,int y,int z) {
    if (y==INT_MAX||z==INT_MAX) return 0;
    int p=0,q=0; if (y<0) p=1,y=-y-1; if (z<0) q=1,z=-z-1;
    y=min(y,siz(h[x][y][z])-1),z=min(z,siz(h[x][y][z][0])-1);
    return h[x][p][q][y][z];
}
void dfs1(int u) {
    F[u]={0,0}; for (auto [v,w]:G[u])
    dfs1(v),F[u]=F[u]+F[v]+get(v,1,p[v][0])+w;
}
void dfs2(int u)
{
    P sum=H[u]; for (auto [v,w]:G[u])
    sum=sum+F[v]+get(v,1,p[v][0])+w;
    for (auto [v,w]:G[u]) {
        P t=F[v]+get(v,1,p[v][0])+w;
        H[v]=sum-t+get(v,0,p[v][0])+w,dfs2(v);
    }
}
main()
{
    n=read(),B=2*sqrt(n);
    for (int i=2;i<=n;i++) g[read()].push_back(i);
    cluster::dfs(1),id[1]=++tot,reverse(a.begin(),a.end() );
    for (int i=1;(1<<i)<=n;i++)
        for (int j=1;j+(1<<i)-1<=n;j++) {
            int x=st[i-1][j],y=st[i-1][j+(1<<i-1)];
            st[i][j]=dep[x]<dep[y]?x:y;
        }
    for (int p=1;p<tot;p++)
    {
        int y=di[p],x=Fa[y]; for (int i=0;i<b[p].size();i++) Id[b[p][i] ]=i;
        for (int o:b[p]) if (o^1) g[fa[o] ].push_back(o),g[o].push_back(fa[o]);
        for (int o:b[p]) {
            dis[o].resize(b[p].size()+1),dfs(o,0,0,o);
            if (p==t) dis[o][0]=dis[o].back();
        }
        for (int o:b[p]) g[o].clear(); g[x].clear();
        int t[2]={Id[y],b[p].size()};
        for (int i:{0,1}) for (int j:{0,1})
        {
            int awa=0; for (int o:b[p])
            awa=max(awa,dis[o][t[j] ]);
            f[p][i][j].resize(awa+1);
            for (int o:b[p]) {
                int x=dis[o][t[j] ],y=dis[o][t[i] ];
                f[p][i][j][x]=f[p][i][j][x]+(P){1,y};
            }
            for (int k=1;k<=awa;k++)
            f[p][i][j][k]=f[p][i][j][k-1]+f[p][i][j-1][k];
        }
        for (int i:{0,1}) for (int j:{0,1})
        {
            int n=f[p][0][i].size(),m=f[p][0][j].size();
            h[p][i][j].resize(n);
            for (int k=0;k<n;k++)
            h[p][i][j][k].resize(m);
            for (int c:b[p]) for (int d:b[p])
            h[p][i][j][dis[c][t[i] ] ][dis[d][t[j] ] ]+=dis[c][Id[d] ];
            for (int c=0;c<n;c++)
                for (int d=1;d<m;d++)
                    h[p][i][j][c][d]+=h[p][i][j][c][d-1];

            for (int c=1;c<n;c++)
                for (int d=0;d<m;d++)
                    h[p][i][j][c][d]+=h[p][i][j][c-1][d];
        }
    }
    for (int i=1;i<tot;i++) {
        int y=di[i],x=Fa[y];
        G[id[x] ].push_back({x,dep[y]-dep[x]});
    }
    m=read();
    while (m--)
    {
        int p0=read(),d0=read(),p1=read(),d1=read(),ans=0;
        for (int i=1;i<tot;i++)
        {
            int y=di[i],x=Fa[y],l,r;
            l=d0-Dis(y,p0),r=d0-Dis(x,p0);
            p[i][0]=l<0&&r<0?INT_MAX:l>r?l:-r-1;
            l=d1-Dis(y,p1),r=d1-Dis(x,p1);
            p[i][1]=l<0&&r<0?INT_MAX:l>r?l:-r-1;
            if (x!=id[p0]&&y!=id[p1]) ans+=Get(i,p[i][0],p[i][1]);
            else
            {
                int c0,c1;
                if (x!=id[p0]) {
                    if (p[i][0]>=0) l=p[i][0],c0=Id[y];
                    else r=-p[i][0]-1,c0=b[i].size();
                }
                else l=d0,c0=Id[p0];
                if (y!=id[p1]) {
                    if (p[i][1]>=0) r=p[i][1],c1=Id[y];
                    else r=-p[i][1]-1,c1=b[i].size();
                }
                else r=d1,c1=Id[p1];
                for (int c:b[i])
                    for (int d:b[i])
                        if (dis[c][c0]<=l&&dis[d][c1]<=r)
                            ans+=dis[c][Id[d] ];
            }
        }
        dfs1(tot),dfs2(tot);
        for (int i=1;i<tot;i++) {
            int x=id[Fa[di[i] ] ];
            ans+=get(i,0,p[i][1])*F[i]+get(i,1,p[i][1])*H[x];
        }
        printf("%lld\n",ans);
    }
    return 0;
}