【HNOI2015】开店 | Mrsrz's blog

动态点分治

题目大意：

给定一棵树，边带边权，点带点权。

每次给出 $u,l,r$，需要回答所有点权在 $l\sim r$ 之间的点到 $u$ 的树上距离之和。

强制在线。

题解：

这map常数真的是大……

建出原树的点分树。

考虑每个查询，都在点分树上直接跳父亲，并求出当前连通块内的点到 $u$ 的距离之和。

建点分树时，我们求出每个连通块中，所有到当前根的路径的信息（结点的点权，到根路径长度），并需要存储根的每个儿子的子树信息。按照点权排序，对到根路径长度求前缀和。

查询的时候，对于一对 $l,r$，我们直接在对应的信息上二分就可以了。

考虑具体的查询过程。

对每个点，其到 $u$ 的距离为其到根的距离，加上 $u$ 到根的距离。这个都可以直接二分统计。

然后还要减去 $u$ 本身所在子树中算重的贡献。

建点分树的时间复杂度为 $O(n\log^2n)$，单次查询的复杂度为 $O(\log^2n)$。

总时间复杂度 $O((n+m)\log^2 n)$，空间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
char buf[(int)1e8],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
const int N=1.6e5;
typedef long long LL;
typedef vector<pair<int,LL> >Data;
int n,m,age[N],head[N],all,rt,mxd[N],sz[N],lim,cnt;
bool vis[N];
LL ans;
struct edge{
    int to,nxt,dis;
}e[N<<1];
void getrt(int now,int pre){
    sz[now]=1,mxd[now]=0;
    for(int i=head[now];i;i=e[i].nxt)
        if(!vis[e[i].to]&&e[i].to!=pre){
            getrt(e[i].to,now);
            sz[now]+=sz[e[i].to];
            mxd[now]=max(mxd[now],sz[e[i].to]);
        }
    mxd[now]=max(mxd[now],all-sz[now]);
    if(!rt||mxd[now]<mxd[rt])rt=now;
}
Data f[N*22];
int nf=0;
int fa[N],id_rt[N],ceng_rt[N];
int nw_ceng;
int dist[19][N],mp[19][N];
pair<int,LL>get_info(int id,int l,int r){
    if(f[id].empty()||f[id].front().first>r)return make_pair(0,0LL);
    int itr=lower_bound(f[id].begin(),f[id].end(),make_pair(r+1,0LL))-f[id].begin()-1;
    int itl=lower_bound(f[id].begin(),f[id].end(),make_pair(l,0LL))-f[id].begin()-1;
    return make_pair(itr-itl,f[id][itr].second-(itl>=0?f[id][itl].second:0));
}
void dfs(int now,int pre,Data&vec,int deep,const int&rt,const int&id){
    vec.push_back(make_pair(age[now],deep));
    dist[nw_ceng][now]=deep;
    mp[nw_ceng][now]=id;
    for(int i=head[now];i;i=e[i].nxt)
        if(e[i].to!=pre&&!vis[e[i].to])
            dfs(e[i].to,now,vec,deep+e[i].dis,rt,id);
}
void doit(int now){
    int&id=id_rt[now];id=++nf;
    for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
        int x=++nf;
        dfs(e[i].to,now,f[x],e[i].dis,now,x);
        sort(f[x].begin(),f[x].end());
        for(int i=0;i<f[x].size();++i)
            f[id].push_back(f[x][i]);
        for(int i=1;i<f[x].size();++i)
            f[x][i].second+=f[x][i-1].second;
    }
    f[id].push_back(make_pair(age[now],0));
    sort(f[id].begin(),f[id].end());
    for(int i=1;i<f[id].size();++i)
        f[id][i].second+=f[id][i-1].second;
}
void build(int now,int ceng){
    ceng_rt[now]=ceng;
    vis[now]=1;
    nw_ceng=ceng;
    doit(now);
    const int sm=all;
    for(int i=head[now];i;i=e[i].nxt)
        if(!vis[e[i].to]){
            all=sz[e[i].to]<sz[now]?sz[e[i].to]:sm-sz[now];
            rt=0;
            getrt(e[i].to,now);
            fa[rt]=now;
            build(rt,ceng+1);
        }
}
void make_tree(){
    all=n;rt=0;
    getrt(1,0);
    build(rt,0);
}
int main(){
    n=readint(),m=readint(),lim=readint();
    for(int i=1;i<=n;++i)age[i]=readint();
    for(int i=1;i<n;++i){
        int u=readint(),v=readint(),w=readint();
        e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
        e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
    }
    make_tree();
    while(m--){
        int u=readint(),l=readint(),r=readint();
        l=(l+ans)%lim,r=(r+ans)%lim;
        if(l>r)swap(l,r);
        ans=0;
        for(int x=u;x;x=fa[x]){
            int c=ceng_rt[x];
            pair<int,LL>al=get_info(id_rt[x],l,r);
            pair<int,LL>sm=(x==u)?make_pair(0,0LL):get_info(mp[c][u],l,r);
            int ct=al.first-sm.first;
            LL len=al.second-sm.second+(ct)*(LL)dist[c][u];
            ans+=len;
        }
        printf("%lld\n",ans);
    }
    return 0;
}