P3241 [HNOI2015]开店

· · 个人记录

\text{Solution}

首先，发现这个东西多询问+询问的东西不关树的形态，那就点分树了。

考虑下，我们如何维护 [L,R] 的 dis ，假如拍扁到序列，我们可以按这个年龄从小到大，然后二分找出区间。

按照这种思想，我们发现由于点度 \le3，我们可以暴力维护每个分治中心的妖怪信息，并按年龄排序，开个vector，类似于序列的做法即可。

然后贡献的话就是这次年龄合法的数量乘上分治中心到x的距离再加上这些点到分治中心的距离和。

\text{Code}

#include <bits/stdc++.h>

#define N (int)(1.5e5+5)
#define int long long
#define inf (int)(2e18)

using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
struct edge {
    int nex,to,w;
}e[N<<1];

struct node {
    int old,cnt,dsum;
    node(int oldd=0ll,int cntt=0ll,int dsumm=0ll) {
        old=oldd; cnt=cntt; dsum=dsumm;
    }
    bool operator < (const node &x) const {
        return old<x.old;
    }
};

struct nodd {
    int dis,rt,typ;
};

vector<node>g[3][N];
vector<nodd>ch[N];
bool vis[N];
int head[N],cnt;
int sz[N],v[N],dis[N];
int n,m,mxA,minn,rt,summ;

void add_edge(int x,int y,int z) {
    e[++cnt]=edge{head[x],y,z};
    head[x]=cnt;
}

void get_sz(int x,int f) {
    sz[x]=1;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        if(y==f||vis[y]) continue;
        get_sz(y,x); sz[x]+=sz[y];
    }
} 

void fd_rt(int x,int f) {
    int mx=summ-sz[x];
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        if(y==f||vis[y]) continue;
        fd_rt(y,x); mx=max(mx,sz[y]);
    }
    if(mx<minn) minn=mx,rt=x;
}

void cal(int x,int fa,int frt,int t) {
    ch[x].push_back(nodd{dis[x],frt,t});
    g[t][rt].push_back(node{v[x],1,dis[x]});
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to; 
        if(y==fa||vis[y]) continue;
        dis[y]=dis[x]+e[i].w;
        cal(y,x,frt,t);
    } 
}

void solve(int x,int f) {
    int tot=0; ch[x].push_back(nodd{0,rt,-1});
    vis[x]=1;
    if(sz[f]==1) return;
    for(int i=head[rt];i;i=e[i].nex) {
        int y=e[i].to;
        if(vis[y]) continue;
        dis[y]=e[i].w;
        cal(y,rt,rt,tot);
        g[tot][rt].push_back(node{inf,0,0});
        sort(g[tot][rt].begin(),g[tot][rt].end());
        for(int i=g[tot][rt].size()-2;i>=0;i--) {
            g[tot][rt][i].cnt+=g[tot][rt][i+1].cnt;
            g[tot][rt][i].dsum+=g[tot][rt][i+1].dsum;
        }
        ++tot; 
    }
    for(int i=head[rt];i;i=e[i].nex) {
        int y=e[i].to;
        if(vis[y]) continue;
        get_sz(y,x); summ=sz[y]; minn=inf; fd_rt(y,x);
        solve(rt,y);
    }
} 

int query(int x,int L,int R) {
    int ans=0;
    for(int i=0;i<ch[x].size();i++) {
        int y=ch[x][i].rt;
        for(int j=0;j<3;j++) {
            if(ch[x][i].typ==j||!g[j][y].size()) continue;
            node qwq=node{L,0,0},qaq=node{R,0,0};
            vector<node>::iterator LL=lower_bound(g[j][y].begin(),g[j][y].end(),qwq);
            vector<node>::iterator RR=upper_bound(g[j][y].begin(),g[j][y].end(),qaq);
            ans+=ch[x][i].dis*(LL->cnt-RR->cnt)+LL->dsum-RR->dsum;
        }
        if(L<=v[y]&&v[y]<=R) ans+=ch[x][i].dis;
    }
    return ans;
}

signed main() {
    n=rd(); m=rd(); mxA=rd();
    for(int i=1;i<=n;i++) v[i]=rd();    
    int x,y,z,L,R,ans=0;
    for(int i=1;i<n;i++) {
        x=rd(); y=rd(); z=rd();
        add_edge(x,y,z); add_edge(y,x,z);
    }
    get_sz(1,0); summ=sz[1]; minn=inf; fd_rt(1,0);
    solve(rt,1);
    while(m--) {
        x=rd(); y=rd(); z=rd();
        L=(y+ans)%mxA; R=(z+ans)%mxA;
        if(L>R) swap(L,R);
        printf("%lld\n",ans=query(x,L,R));
    }
    return 0;
}