萌新妹子求调(wa)
查看原帖
萌新妹子求调(wa)
1046894
hyxgg楼主2024/8/10 15:39
#include<iostream>
#include<cmath>
#define ll long long
#define N 1000005
using namespace std;
struct edge
{
    ll q,z,xg,bq;
}ed[N<<1];
struct xds
{
    ll z,g,ls,rs;
}yd[60*N];
ll n,q,db=1,dd[N],a[N],b[N],a1[N],a2[N],gs[N],dfn[N],df[N],zz[N],sd[N],fa[N],tot,rt[N],cnt,jl[N];
void fjq(ll q,ll z,ll b){
    ed[db].bq=b,ed[db].z=z,ed[db].q=q,ed[db].xg=dd[q],dd[q]=db++;
}
void dfs1(ll root){
    gs[root]=1;
    ll mx=0;
    for(ll i=dd[root];i;i=ed[i].xg){
        ll to=ed[i].z;
        if(to==fa[root])continue;
        fa[to]=root;
        sd[to]=sd[root]+1;
        jl[to]=jl[root]+ed[i].bq;
        dfs1(to);
        gs[root]+=gs[to];
        if(mx<gs[to])zz[root]=to,mx=gs[to];
    }
}
void dfs2(ll root,ll d){
    df[root]=d;
    dfn[root]=++tot;
    if(zz[root])dfs2(zz[root],d);
    for(ll i=dd[root];i;i=ed[i].xg){
        ll to=ed[i].z;
        if(to==fa[root]||to==zz[root])continue;
        dfs2(to,to);
    }
}
void gd(ll& b,ll x,ll z,ll l,ll r){
    if(!b)b=++cnt;
    if(l==r){
        yd[b].z=z;
        yd[b].g=1;
        return ;
    }
    ll mid=(l+r)>>1;
    if(x<=mid)gd(yd[b].ls,x,z,l,mid);
    else gd(yd[b].rs,x,z,mid+1,r);
    yd[b].z=yd[yd[b].ls].z+yd[yd[b].rs].z;
    yd[b].g=yd[yd[b].ls].g+yd[yd[b].rs].g;
}
ll cx(ll b,ll x,ll y,ll l,ll r,ll z){
    if(!b)return 0;
    if(l>=x&&r<=y){
        return z*yd[b].g-yd[b].z;
    }
    ll mid=(l+r)>>1,s=0;
    if(y>mid)s+=cx(yd[b].rs,x,y,mid+1,r,z);
    if(x<=mid)s+=cx(yd[b].ls,x,y,l,mid,z);
    return s;
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<n;i++){
        scanf("%lld%lld%lld%lld",&a1[i],&a2[i],&a[i],&b[i]);
        fjq(a1[i],a2[i],b[i]),fjq(a2[i],a1[i],b[i]);
    }
    dfs1(1);
    dfs2(1,1);
    for(ll i=1;i<n;i++){
        ll aa=sd[a1[i]]>sd[a2[i]]?a1[i]:a2[i];
        gd(rt[a[i]],dfn[aa],b[i],1,n);
    }
    ll aa,bb,cc,dd;
    for(ll i=1;i<=q;i++){
        scanf("%lld%lld%lld%lld",&aa,&bb,&cc,&dd);
        ll ans=jl[cc]+jl[dd];
        while(df[cc]!=df[dd]){
            if(sd[df[cc]]>sd[df[dd]]){
                ans+=cx(rt[aa],dfn[df[cc]],dfn[cc],1,n,bb);
                cc=fa[df[cc]];
            }
            else{
                ans+=cx(rt[aa],dfn[df[dd]],dfn[dd],1,n,bb);
                dd=fa[df[dd]];
            }
        }
        if(sd[cc]>sd[dd])swap(cc,dd);
        ans-=2ll*jl[cc];
        ans+=cx(rt[aa],dfn[cc],dfn[dd],1,n,bb);
        printf("%lld\n",ans);
    }
    return 0;
}
2024/8/10 15:39
加载中...