[HNOI2015] 開店

「前言」為防止在某巨巨的毒瘤idea 紫荊花之“店" 面前一臉懵，特滾來補此題。 我還是太naive了。

「題義」給出一棵單點度數很小的無根帶邊權、點權的樹，每次詢問在所有點權在[l,r]的點到c的距離之和。

「分析」考慮建立點分樹，分治結構每個點都儲存對應分治範圍（簡稱範圍）內的信息，詢問時從c向後跳分治鏈，並逐級將信息合併得到整棵樹的答案。

對於鏈上某一點x，設前一個點為px，顯然我們需要用到的，x範圍中（除去px範圍）的所有合法的點（即點權在[l,r]內的點）到c的距離之和，拆開為這些點到x的距離和+這些點的個數乘以x到c的距離。對於第一部分我們將它看作x範圍內所有點到x的距離和-px範圍內所有點到x的距離和，第二部分同理。

這樣，我們只需要對每個節點x儲存範圍內所有點點權age、到x的距離dis以及到上一級分治中心fa[x]的距離ldis（放在集合d[x]）。然後將d[x]按照age排序，那麼x的分治範圍對於查詢中心c的產生貢的點獻處於d[x]的一段區間上。利用前（後）綴和+二分就能地很好處理了。

#include <bits/stdc++.h>
#define IL inline 
#define LL long long 
using namespace std;

const int N=150010;
const int inf=0x3f3f3f3f;

int n,Q,A,age[N];
int head[N],to[N<<1],last[N<<1],len[N<<1];

IL void addEdge(int x,int y,int w) {
    static int cnt=0;
    to[++cnt]=y,len[cnt]=w,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,len[cnt]=w,last[cnt]=head[y],head[y]=cnt;
}
namespace dbl {
    int fa[N][20],dep[N];
    LL ds[N][20];
    void prDfs(int x,int d) {
        dep[x]=dep[fa[x][0]=d]+1;
        for(int i=1; (1<<i)<=dep[x]; ++i) {
            fa[x][i]=fa[fa[x][i-1]][i-1];
            ds[x][i]=ds[fa[x][i-1]][i-1]+ds[x][i-1];
        }
        for(int i=head[x]; i; i=last[i]) {
            if(to[i]!=d) ds[to[i]][0]=len[i],prDfs(to[i],x);
        }
    }
    IL LL gtDis(int x,int y) {
        if(dep[x]<dep[y]) swap(x,y);
        LL ret=0; int dif=dep[x]-dep[y];
        for(int i=19; ~i; --i) if((dif>>i)&1) 
            ret+=ds[x][i],x=fa[x][i];
        if(x==y) return ret;
        for(int i=19; ~i; --i) if(fa[x][i]!=fa[y][i]) 
            ret+=ds[x][i],x=fa[x][i],ret+=ds[y][i],y=fa[y][i];
        return ret+ds[x][0]+ds[y][0];
    }
}
namespace dpd {
    struct node {
        LL dis,ldis; int age;
        IL node(LL d=0,LL ld=0,int a=0):dis(d),ldis(ld),age(a){}    
        IL bool operator<(const node&d) const {
            return age<d.age;
        }
    };
    vector<node> d[N];
    int root,siz[N],fa[N];
    bool ban[N];
    void prSiz(int x,int d) {
        siz[x]=1; 
        for(int i=head[x]; i; i=last[i]) if(!ban[to[i]]&&to[i]!=d) 
            prSiz(to[i],x),siz[x]+=siz[to[i]];
    }
    void gtRoot(int x,int d,int t) {
        static int f[N]={inf}; f[x]=siz[t]-siz[x];
        for(int i=head[x]; i; i=last[i]) if(!ban[to[i]]&&to[i]!=d) 
            gtRoot(to[i],x,t),f[x]=max(f[x],siz[to[i]]);
        if(f[x]<f[root]) root=x;
    }
    void prNode(int x,int d,LL dis) {
        dpd::d[root].push_back(node(dis,dbl::gtDis(x,fa[root]),age[x]));
        for(int i=head[x]; i; i=last[i]) {
            if(!ban[to[i]]&&to[i]!=d) prNode(to[i],x,dis+len[i]);
        }
    }
    void build(int x,int lrt) {
        root=0; prSiz(x,0); gtRoot(x,0,x); 
        x=root; fa[x]=lrt; ban[x]=1; prNode(x,0,0);
        sort(d[x].begin(),d[x].end());
        d[x].push_back(node(0,0,A));
        for(unsigned i=d[x].size()-2; ~i; --i) {
            d[x][i].dis+=d[x][i+1].dis;
            d[x][i].ldis+=d[x][i+1].ldis;
        }
        for(int i=head[x]; i; i=last[i]) {
            if(!ban[to[i]]) build(to[i],x);
        }
    }
    IL LL query(int c,int l,int r) {
        vector<node>::iterator L,R; LL ans=0;
        for(int x=c; x; x=fa[x]) {
            L=lower_bound(d[x].begin(),d[x].end(),node(0,0,l));
            R=upper_bound(d[x].begin(),d[x].end(),node(0,0,r));
            ans+=dbl::gtDis(x,c)*(R-L)+(L->dis-R->dis);
            if(fa[x]) ans-=dbl::gtDis(fa[x],c)*(R-L)+(L->ldis-R->ldis);
        }
        return ans;
    }
}

int main() {
    scanf("%d%d%d",&n,&Q,&A);
    for(int i=1; i<=n; ++i) scanf("%d",&age[i]);
    for(int x,y,w,i=n; --i; ) {
        scanf("%d%d%d",&x,&y,&w);
        addEdge(x,y,w);
    }
    dbl::prDfs(1,0);
    dpd::build(1,0); 
    LL lans=0;
    for(int u,a,b; Q--; ) {
        scanf("%d%d%d",&u,&a,&b);
        a=(lans+a)%A, b=(lans+b)%A; if(a>b) swap(a,b); 
        printf("%lld\n",lans=dpd::query(u,a,b));
    }
    return 0;
} // 代碼O2需要

好了，滾去看 紫荊花之戀 了