传送门

这题北京集训的时候做过。。。

大概就是先按dfs序和深度把每个点表示在一个二维平面上,然后一个询问覆盖到的点就是一个矩形内的点。我们把这些点的KD树建出来,这样每次询问覆盖到的节点数量就是$O(\sqrt n)$级别的。操作之后的节点我们可以打上标记,然后如果一次询问中发现子树里面存在之前的标记,就暴力搜索下去,把标记都清除,并更新答案。这样每添加一个标记,最多会花费$O(\log n)$的时间去清除它(这个log是KD树的树高)。所以总复杂度就是$O(n\sqrt n\log n)$的。相信KD树常数很小的话就能过啦!

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#define LL long long
#define MAXN 100010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9')
        res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next;
    LL w;
    edge(int _to=0,int _next=0,LL _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m;
int w[MAXN][2],numw=0;
int g[MAXN],nume=0;
LL v[MAXN],lim[MAXN],d[MAXN];
LL q[MAXN][3];
int p[MAXN];

int debug=0;

namespace SegTree{
    struct node{
        LL s1,s2;
        int lc,rc;
    }a[7000000];

    int size;
    LL sizew;

    void init(){
        size=0;
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++)
            sizew=max(sizew,(lim[i]-1)/v[i]+1);
    }

    int create(int l,int r,int p,LL v1,LL v2){
        int x=++size;
        a[x].s1=v1;
        a[x].s2=v2;
        if(l==r) return x;
        int mid=(l+r)>>1;
        if(p<=mid) a[x].lc=create(l,mid,p,v1,v2);
        else a[x].rc=create(mid+1,r,p,v1,v2);
        return x;
    }

    int join(int x,int y){
        if(!x) return y;
        if(!y) return x;
        int z=++size;
        a[z].s1=a[x].s1+a[y].s1;
        a[z].s2=a[x].s2+a[y].s2;
        a[z].lc=join(a[x].lc,a[y].lc);
        a[z].rc=join(a[x].rc,a[y].rc);
        return z;
    }

    LL getS1(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r) return a[x].s1;
        int mid=(cl+cr)>>1;
        LL res=0;
        if(l<=mid)
            res+=getS1(a[x].lc,l,r,cl,mid);
        if(r>mid)
            res+=getS1(a[x].rc,l,r,mid+1,cr);
        return res;
    }

    LL getS2(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r) return a[x].s2;
        int mid=(cl+cr)>>1;
        LL res=0;
        if(l<=mid)
            res+=getS2(a[x].lc,l,r,cl,mid);
        if(r>mid)
            res+=getS2(a[x].rc,l,r,mid+1,cr);
        return res;
    }
}

namespace KD_Tree{
    struct point{
        int id;
        LL x,y;
        LL t1,t2,t3;
    }p[MAXN];

    bool cmpx(point x,point y){ return x.x<y.x; }
    bool cmpy(point x,point y){ return x.y<y.y; }

    struct node{
        int lc,rc,p,l,r;
        int seg_root;
        bool tag;
        LL delta_t;
        LL minx,maxx,miny,maxy;
    }a[MAXN<<1];

    int size;
    LL total_delta_t;

    int build(int l,int r,int d){
        if(!d)
            sort(p+l,p+r+1,cmpx);
        else
            sort(p+l,p+r+1,cmpy);
        int x=++size;
        a[x].l=l;
        a[x].r=r;
        a[x].minx=a[x].maxx=p[l].x;
        a[x].miny=a[x].maxy=p[l].y;
        for(int i=l+1;i<=r;i++){
            if(p[i].x<a[x].minx) a[x].minx=p[i].x;
            if(p[i].x>a[x].maxx) a[x].maxx=p[i].x;
            if(p[i].y<a[x].miny) a[x].miny=p[i].y;
            if(p[i].y>a[x].maxy) a[x].maxy=p[i].y;
        }
        if(l==r){
            p[l].t1=(lim[p[l].id]-1)/v[p[l].id]+1;
            p[l].t2=lim[p[l].id];
            p[l].t3=v[p[l].id];
            a[x].seg_root=SegTree::create(1,SegTree::sizew,p[l].t1,p[l].t2,p[l].t3);
            return x;
        }
        int mid=(l+r)>>1;
        a[x].lc=build(l,mid,d^1);
        a[a[x].lc].p=x;
        a[x].rc=build(mid+1,r,d^1);
        a[a[x].rc].p=x;
        a[x].seg_root=SegTree::join(a[a[x].lc].seg_root,a[a[x].rc].seg_root);
        return x;
    }

    void init(){
        SegTree::init();
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++)
            p[i].x=w[i][0],p[i].y=d[i],p[i].id=i;
        size=0;
        build(1,n,0);
        a[1].p=0;
        total_delta_t=0;
    }

    bool collide(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(minx>a[x].maxx) return 0;
        if(miny>a[x].maxy) return 0;
        if(maxx<a[x].minx) return 0;
        if(maxy<a[x].miny) return 0;
        return 1;
    }

    bool contain(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(minx>a[x].minx) return 0;
        if(miny>a[x].miny) return 0;
        if(maxx<a[x].maxx) return 0;
        if(maxy<a[x].maxy) return 0;
        return 1;
    }

    LL query(int x,LL t){
        if(a[x].r-a[x].l+1<=70){
            LL res=0;
            for(int i=a[x].l;i<=a[x].r;i++)
                res+=(p[i].t1<=t)?(p[i].t2):(p[i].t3*t);
            return res;
        }
        LL res=0;
        if(t)
            res+=SegTree::getS1(a[x].seg_root,1,t,1,SegTree::sizew);
        if(t<SegTree::sizew)
            res+=SegTree::getS2(a[x].seg_root,t+1,SegTree::sizew,1,SegTree::sizew)*t;
        return res;
    }

    LL res_gao;

    void dfs(int x){
        a[x].tag=0;
        if(a[x].delta_t){
            res_gao-=query(x,total_delta_t);
            res_gao+=query(x,total_delta_t+a[x].delta_t);
            a[x].delta_t=0;
        }else{
            if(a[a[x].lc].tag) dfs(a[x].lc);
            if(a[a[x].rc].tag) dfs(a[x].rc);
        }
    }

    LL gao(int x){
        res_gao=query(x,total_delta_t);
        if(a[x].tag)
            dfs(x);
        a[x].delta_t=-total_delta_t;
        a[x].tag=1;
        if(a[x].p && !a[a[x].p].tag){
            for(int i=a[x].p;i;i=a[i].p)
                a[i].tag=1;
        }
        return res_gao;
    }

    void pushdown(int x){
        if(!a[x].delta_t) return;
        a[a[x].lc].tag=1;
        a[a[x].rc].tag=1;
        a[a[x].lc].delta_t=a[x].delta_t;
        a[a[x].rc].delta_t=a[x].delta_t;
        a[x].delta_t=0;
    }

    LL gao(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(!collide(x,minx,miny,maxx,maxy)) return 0;
        if(contain(x,minx,miny,maxx,maxy)) return gao(x);
        pushdown(x);
        LL res=0;
        if(a[x].lc) res+=gao(a[x].lc,minx,miny,maxx,maxy);
        if(a[x].rc) res+=gao(a[x].rc,minx,miny,maxx,maxy);
        return res;
    }
}

void addEdge(int u,int v,LL w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void dfs(int x,int p){
    w[x][0]=++numw;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            d[e[i].to]=d[x]+e[i].w;
            dfs(e[i].to,x);
        }
    w[x][1]=numw;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("C.in","r",stdin);
    #endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int i=1;i<=n;i++)
        lim[i]=read();
    d[1]=d[0]=0;
    for(int i=2;i<=n;i++){
        p[i]=read();
        d[i]=read();
        addEdge(p[i],i,d[i]);
    }
    dfs(1,0);
    KD_Tree::init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        q[i][0]=read();
        q[i][1]=read();
        q[i][2]=read();
    }
    for(int i=1;i<=m;i++){
        KD_Tree::total_delta_t=q[i][0];
        printf("%lld\n", KD_Tree::gao(1,w[q[i][1]][0],d[q[i][1]],w[q[i][1]][1],d[q[i][1]]+q[i][2]));
    }
    return 0;
}