Problem

给定一个无根带边权树，每个点有一个权值
每次给定询问 u，l，r，询问权值范围在 [l,r] 的点到 u 的距离之和

Solution

先吐槽一下，luogu 只给开 3s，不开 O2 过不了系列

本题有两种做法，一种主席树神秘做法，一种动态点分治
动态点分治的做法是在点分治的基础上，对每个重点加上一个 fa[x]，即重点的父亲
等价于重构一个点分树

那么当要进行多次查询的时候，往上找的话，最多只要查询 $\log n$ 个点
进行多次修改的话，也是一样的道理
对于每个点的查询，均摊下来也是 $n\log n$ 的复杂度
所以总复杂度是 $O(n\log ^2n)$

这样子的查询也保证是照顾到全部树的

假设不对颜色进行限制
对于本题，在某一层的点分治中，对多个不同的子树进行处理
假设 u 在其中的一个子树中，那么其它子树的点到根节点的距离之和+（其它子树的点的个数+1）×根节点到u的距离，这就是这一层子树对答案的贡献

对颜色进行限制之后，只需要将每一个子树的序列求下来，前缀和加 lr 套进去二分就行

距离的话就用树剖

实现的话 vector 各种乱搞

简单来说空间时间期望复杂度就是 $O(n\log ^3n)$
代码复杂度很傻比，我也不知道有没有更好的做法 \_(:зゝ∠)_

Code

// Code by ajcxsu
// Problem: HNOI2015 Open Shop

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
const int N=1.5e5+10,M=3e5+10;
int h[N],to[M],nexp[M],p=1;
ll W[M];
inline void ins (int a,int b,int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
int old[N];
ll fdep[N];

namespace Dis {
    int dfn[N], son[N], siz[N], fa[N], idx;
    int dep[N], top[N];
    void dfs1(int x,int k) {
        dep[x]=k, siz[x]=1;
        for(int u=h[x];u;u=nexp[u])
            if(!dep[to[u]]) {
                fa[to[u]]=x;
                dfs1(to[u], k+1);
                siz[x]+=siz[to[u]];
                if(siz[son[x]]<siz[to[u]]) son[x]=to[u];
            }
    }
    void dfs2(int x,int t) {
        top[x]=t; dfn[x]=++idx;
        if(son[x]) dfs2(son[x], t);
        for(int u=h[x];u;u=nexp[u])
            if(!dfn[to[u]]) dfs2(to[u],to[u]);
    }
    void init() { dfs1(1,1), dfs2(1,1); }
    int lca(int x,int y) {
        while(top[x]!=top[y]) {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            x=fa[top[x]];
        }
        if(dep[x]>dep[y]) return y;
        else return x;
    }
    int dis(int s,int t) {
        int l=lca(s,t);
        return fdep[s]+fdep[t]-2*fdep[l];
    }
} // 树剖...


template<typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

struct Ele {
    int a; ll dep;
};
bool operator < ( const Ele &a, const Ele &b ) { return a.a<b.a; }
bool operator < ( const Ele &a, const int &b ) { return a.a<b; }
bool operator < ( const int &a, const Ele &b ) { return a<b.a; }
const int OP=60;
typedef vector<Ele> vele;
vele seq[N*OP];
int rp;
vector<vele*> sons[N];
vector<int> sonsid[N];
int fa[N];

void dfs(int x, int fa, ll dep)  {
    fdep[x]=dep;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fa) dfs(to[u], x, dep+W[u]);
}

bool vis[N];
int siz[N], hvy, minn, S;
void ghvy(int x, int fa) {
    siz[x]=1;
    int ma=0;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fa && !vis[to[u]]) {
            ghvy(to[u], x);
            siz[x]+=siz[to[u]];
            ma=max(ma, siz[to[u]]);
        }
    ma=max(ma, S-siz[x]);
    if(ma<minn) minn=ma, hvy=x;
}

void gdep(int x, int fa, ll dep, vele* p ) {
    p->push_back((Ele){old[x],dep});
    for(int u=h[x];u;u=nexp[u])
        if(!vis[to[u]] && to[u]!=fa) {
            gdep(to[u], x, dep+W[u], p);
        }
}

void gseq(int x, int nd, vele* p) {
    gdep(x, 0, nd, p);
    p->push_back((Ele){-1,0});
    sort(p->begin(), p->end());
    for(int i=1, len=p->size(); i<len;i++) {
        (*p)[i].dep+=(*p)[i-1].dep;
    }
}

void gans(int x) {
    vis[x]=1;
    vele* np;
    for(int u=h[x];u;u=nexp[u])
        if(!vis[to[u]]) {
            np=&seq[rp++], sons[x].push_back(np);
            ghvy(to[u], 0); // 先获取该联通块的大小
            S=siz[to[u]], minn=INF;
            ghvy(to[u], 0);
            fa[hvy]=x;
            sonsid[x].push_back(hvy);

            gseq(to[u], W[u], np);
            gans(hvy);
        }
}

ll query(int x, int nl, int nr) {
    int from=0,u=x;
    ll ret=0, dis=0;
    while(x) {
        for(int i=0, len=sons[x].size(); i<len; i++)
            if(sonsid[x][i]!=from) {
                vele* np=sons[x][i];
                vele::iterator l=lower_bound(np->begin(), np->end(), nl)-1, r=upper_bound(np->begin(), np->end(), nr)-1;
                ret+=r->dep - l->dep + 1ll * (r-l) * dis;
            }
        if(old[x]>=nl && old[x]<=nr) ret+=dis;
        dis=Dis::dis(fa[x], u);
        from=x, x=fa[x];
    }
    return ret;
}

int main() {
    int n,Q;
    ll A;
    gn(n), gn(Q), gn(A);
    for(int i=1;i<=n;i++) gn(old[i]);
    int u,v,w;
    for(int i=1;i<=n-1;i++) gn(u), gn(v), gn(w), ins(u,v,w), ins(v,u,w);
    Dis::init();
    gans(1);
    dfs(1, 0, 0);
    ll ans=-1;
    ll a,b;
    ll l,r;
    while(Q--) {
        gn(u), gn(a), gn(b);
        if(ans==-1) l=min(a%A, b%A), r=max(a%A, b%A);
        else l=min((a+ans) % A, (b+ans) % A), r=max((a+ans) % A, (b+ans) % A);
        printf("%lld\n", ans=query(u,l,r));
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3241.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆