RT

在李超树的 upd 中给 x 赋值时，大概 tcnt 达到 20 多就会奇妙 RE，有没有佬帮忙看看。

#include <algorithm>
#include <iostream>
#include <cstdio>

#define N 200001
#define LL long long

using namespace std;
int n,T,maxn,fa[N],p[N]; LL _l[N],q[N],f[N];

int cnt,head[N];
struct Node { int to,nxt; LL dis; }e[N];

void add(int u,int v,LL w) { e[++cnt]=Node{v,head[u],w},head[u]=cnt; }

struct LCT {
    int tcnt,rt[N<<2];
    struct Tree { LL k,b; int ls,rs; }t[N<<6];

    void upd(int &x,int l,int r,LL k,LL b) {
        if (!x) t[x=++tcnt]={(LL)-1e9,(LL)-1e9,0,0};
        int mid=(l+r>>1);
        if (t[x].k*mid+t[x].b<k*mid+b) swap(t[x].k,k),swap(t[x].b,b);
        // if (l==r) return; 
        LL tmpl=k*l+b-t[x].k*l-t[x].b,tmpr=k*r+b-t[x].k*r-t[x].b;
        if (tmpl>0 or (!tmpl and k>t[x].k)) upd(t[x].ls,l,mid,k,b);
        if (tmpr>0 or (!tmpr and k>t[x].k)) upd(t[x].rs,mid+1,r,k,b);
    }

    LL ask(int x,int l,int r,int pos) {
        if (!x) return 0;
        if (l==r) return t[x].k*pos+t[x].b;
        LL res=t[x].k*pos+t[x].b; int mid=(l+r>>1);
        if (pos<=mid) return max(res,ask(t[x].ls,l,mid,pos));
        else return max(res,ask(t[x].rs,mid+1,r,pos));
    }
}lct;

void upd(int x,int l,int r,int pos,LL k,LL b) {
    lct.upd(lct.rt[x],0,maxn,k,b);
    if (l==r) return;
    int mid=(l+r>>1);
    if (pos<=mid) upd(x<<1,l,mid+1,pos,k,b);
    else upd(x<<1|1,mid+1,r,pos,k,b);
}

LL ask(int x,int l,int r,int L,int R,int k) {
    if (L<=l and r<=R) return lct.ask(lct.rt[x],0,maxn,k);
    int mid=(l+r>>1); LL res=0;
    if (L<=mid) res=max(res,ask(x<<1,l,mid,L,R,k));
    if (R>mid) res=max(res,ask(x<<1|1,mid+1,r,L,R,k));
    return res;
}

int idcnt,siz[N],son[N],dep[N],top[N],id[N],nid[N]; LL dis[N],tdis[N];

void dfs1(int u) {
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        dis[v]=dis[u]+e[i].dis;
        dfs1(v);
        siz[u]+=siz[v];
        if (siz[v]>siz[son[u]]) son[u]=v;
    }
}

void dfs2(int u,int Top) {
    top[u]=Top,nid[id[u]=++idcnt]=u,tdis[id[u]]=dis[u];
    if (son[u]) dfs2(son[u],Top);
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if (v==son[u]) continue;
        dfs2(v,v);
    }
}

LL ask(int x) {
    int tx=x; LL res=0;
    while (x) {
        int l=id[top[x]],r=id[x];
        if (dis[tx]-tdis[l]>_l[tx]) {
            l=lower_bound(tdis+l,tdis+r+1,dis[tx]-_l[tx])-tdis-l+1;
            res=max(res,ask(1,1,n,l,r,p[tx]));
            break;
        } else {
            res=max(res,ask(1,1,n,l,r,p[tx]));
            x=fa[top[x]];
        }
    }
    return res;
}

int main() {
    scanf("%d%d",&n,&T);
    for (int i=2;i<=n;i++) {
        LL x;
        scanf("%d%lld%d%lld%lld",fa+i,&x,p+i,q+i,_l+i);
        add(fa[i],i,x); maxn=max(maxn,p[i]);
    }
    dfs1(1); dfs2(1,1);
    // printf("1\n");
    for (int i=2;i<=n;i++) {
        f[nid[i]]=ask(nid[i])+q[nid[i]]+1ll*p[nid[i]]*dis[nid[i]];
        upd(1,1,n,i,-dis[nid[i]],f[nid[i]]);
    }
    for (int i=2;i<=n;i++) printf("%d\n",f[i]);
    return 0;
}