Description

风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 n个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 u（u为编号），然后在 u开一家面向年龄在 L到R 之间（即年龄大于等于 L、小于等于 R）的妖怪的店。也有可能 u这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪，到点 u 的距离的和是多少（妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和） ，幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。

Input

第一行三个用空格分开的数 n、Q和A，表示树的大小、开店的方案个数和妖怪的年龄上限。

第二行n个用空格分开的数 x_1、x_2、…、x_n，x_i 表示第i 个地点妖怪的年龄，满足0<=x_i<A。(年龄是可以为 0的，例如刚出生的妖怪的年龄为 0。)

接下来 n-1 行，每行三个用空格分开的数 a、b、c，表示树上的顶点 a 和 b 之间有一条权为c(1 <= c <= 1000)的边，a和b 是顶点编号。

接下来Q行，每行三个用空格分开的数 u、 a、 b。对于这 Q行的每一行，用 a、b、A计算出 L和R，表示询问“在地方 u开店，面向妖怪的年龄区间为[L,R]的方案的方便值是多少”。对于其中第 1 行，L 和 R 的计算方法为：L=min(a%A,b%A), R=max(a%A,b%A)。对于第 2到第 Q行，假设前一行得到的方便值为 ans，那么当前行的 L 和 R 计算方法为： L=min((a+ans)%A,(b+ans)%A), R=max((a+ans)%A,(b+ans)%A)。

Output

对于每个方案，输出一行表示方便值。

Sample Input

10 10 10 0 0 7 2 1 4 7 7 7 9  1 2 270 2 3 217 1 4 326 2 5 361 4 6 116 3 7 38 1 8 800 6 9 210 7 10 278 8 9 8 2 8 0 9 3 1 8 0 8 4 2 7 9 7 3 4 7 0 2 2 7 3 2 1 2 3 4

Sample Output

1603 957 7161 9466 3232 5223 1879 1669 1282 0

Solution

动态点分治。

其实这题比较模板了...建出点分树，对每个分治块记录一个数组，数组每个元素记录两个信息：这个点距离当前分治中心的距离\(dis\)和颜色\(c\)，然后按照颜色排序，对\(dis\)前缀和，这样可以方便后面计算。

然后对当前分治中心的每个儿子也记录同样的信息，即以当前分治中心为根的子树的\(dis\)和\(c\)。

那么每次查询沿着点分树往上跳，然后在数组上二分得到答案，每次减去某个儿子的答案就好了。

复杂度\(O(n\log^2 n)\)。

细节挺多的...我是感觉\(vector\)比较慢就手写的动态分配空间，代码有点精神污染...

#include
    
     using namespace std; #define ll long longvoid read(int &x) {    x=0;int f=1;char ch=getchar();    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;} void print(ll x) {    if(x<0) putchar('-'),x=-x;    if(!x) return ;print(x/10),putchar(x%10+48);}void write(ll x) {if(!x) putchar('0');else print(x);putchar('\n');}#define lf doubleconst int maxn = 2e5+10;const int inf = 1e9;const lf eps = 1e-8;ll lstans;int head[maxn],tot,fa[maxn],sp,col[maxn],n,q,A,rt,sz[maxn],d[maxn],size,vis[maxn],SZ[maxn];struct edge{int to,nxt,w;}e[maxn<<1];struct data{    ll v;int c;    bool operator < (const data &rhs) const {return c
     
      =dep[y]) x=g[x][i];        if(x==y) return x;        for(int i=18;~i;i--) if(g[x][i]!=g[y][i]) x=g[x][i],y=g[y][i];        return g[x][0];    }    ll dis(int x,int y) {return dist[x]+dist[y]-2*dist[lca(x,y)];}}T;void get_rt(int x,int Fa) {    sz[x]=1,d[x]=0;    for(int i=head[x];i;i=e[i].nxt)        if(e[i].to!=Fa&&!vis[e[i].to]) {            get_rt(e[i].to,x),sz[x]+=sz[e[i].to];            if(d[x]
      
       d[x]) rt=x;}int now;void dfs(int x,int Fa,ll dis,data *r) {    r[++now]=(data){dis,col[x]};    for(int i=head[x];i;i=e[i].nxt)        if(e[i].to!=Fa&&!vis[e[i].to]) dfs(e[i].to,x,dis+e[i].w,r);}void solve(int x) {    vis[x]=1,get_rt(x,0),size=sz[x];    f[x]=space+sp;sp+=size+2;now=0;SZ[x]=size;    dfs(x,0,0,f[x]);    sort(f[x]+1,f[x]+size+1);    for(int i=1;i<=size;i++) f[x][i].v+=f[x][i-1].v;    for(int i=head[x],cnt=0;i;i=e[i].nxt,cnt++)        if(!vis[e[i].to]) {            now=0,dfs(e[i].to,x,e[i].w,s[x][cnt]=space+sp),sp+=sz[e[i].to]+3;            if(sz[e[i].to]) {                sort(s[x][cnt]+1,s[x][cnt]+sz[e[i].to]+1);                for(int j=1;j<=sz[e[i].to];j++)                    s[x][cnt][j].v+=s[x][cnt][j-1].v;            }        }    for(int i=head[x],cnt=0;i;i=e[i].nxt,cnt++)        if(!vis[e[i].to]) {            get_rt(e[i].to,x);size=sz[e[i].to],rt=0;get_rt(e[i].to,x);            fa[rt]=x;tr[x][cnt]=rt,solve(rt);        }}ll calc(data *r,int Sz,int l,int R,int op,ll D) {    int i=upper_bound(r+1,r+Sz+1,R)-r;i--;    if(!i) return 0;    int j=lower_bound(r+1,r+Sz+1,l)-r;j--;    return r[i].v-r[j].v+op*D*(i-j);}ll query(int u,int l,int r) {    rt=u;ll res=calc(f[u],SZ[u],l,r,0,0);int pre=u;u=fa[u];    for(;u;pre=u,u=fa[u]) {        res+=calc(f[u],SZ[u],l,r,1,T.dis(u,rt));        for(int i=0;i<3;i++)            if(tr[u][i]==pre) res-=calc(s[u][i],SZ[pre],l,r,1,T.dis(u,rt));    }return res;}int main() {    read(n),read(q),read(A);    for(int i=1;i<=n;i++) read(col[i]);    for(int i=1,x,y,z;i