1.遇到一个问题：先处理子树内部，再处理子树之间

2.树的重心：删除重心之后，相比于删除其他点，分出来的每个连通块的数量的最大值最小
最大值一定<=$\frac{n}{2}$

3.树:
求任意两点间，长度<k有多少条
题解：

找出重心

删掉重心

1.如果两个端点在同一个子树内：递归处理

2.在不同子树内：
路径肯定会经过重心。
先预处理每个点到重心的距离
从中任选两点，看看距离<k有多少个（排序+二分）
然后减去两点在同一子树

3.有一点是重心:dfs

4.权值：求一条路径权值和=k，包含边最少
题解：照旧

找出重心

删掉重心

1.如果两个端点在同一个子树内：递归处理

2.在不同子树内：
开个桶记录距离重心长度为x的边数最小值f(x)
然后就像上一题那样

3.有一点是重心:dfs

5.点分树：有一个点U，求所有年龄在[L,R]之间，与U的距离之和

 #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 150010,M=N*2;

int n,m,A;//A 年龄上限
int h[N], e[M], w[M], ne[M], idx;
int age[N];
bool st[N];
struct Father
{
    int u,num;//重心下标u,哪个子树，子树的编号num
    LL dist;//父节点距离
};
vector<Father> f[N];
struct Son
{
    int age;
    LL dist;//子树的年龄和距离
    bool operator <(const Son &t) const
    {
        return age<t.age;
    }
};
vector<Son> son[N][3];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u,int fa) //求子树大小
{
    if(st[u]) return 0;
    int res=1;
    for(int i=h[u];~i;i=ne[i])
        if(e[i]!=fa)
            res+=get_size(e[i],u);
    return res;
}

int get_wc(int u,int fa,int tot,int &wc)//求重心，tot总点数，wc是重心
{
    if(st[u]) return 0;
    int sum=1,ms=0;//sum 当前子树大小，ms 删除当前节点后，剩余连通块最大值
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        int t=get_wc(j,u,tot,wc);
        ms=max(ms,t);
        sum+=t;
    }
    ms=max(ms,tot-sum);
    if(ms<=tot/2) wc=u;
    return sum;
}

void get_dist(int u,int fa,LL dist,int wc,int k,vector<Son> &p)
{
    if(st[u]) return;
    f[u].push_back({wc,k,dist});
    p.push_back({age[u],dist});
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        get_dist(j,u,dist+w[i],wc,k,p);
    }
}

void calc(int u)
{
    if(st[u]) return;
    get_wc(u,-1,get_size(u,-1),u);
    st[u]=1;
    for(int i=h[u],k=0;~i;i=ne[i])//k是子树编号
    {
        int j=e[i];
        if(st[j]) continue;
        auto &p=son[u][k];
        p.push_back({-1,0}),p.push_back({A+1,0});//哨兵
        get_dist(j,-1,w[i],u,k,p);
        k++;
        sort(p.begin(),p.end());
        for(int i=1;i<p.size();i++) p[i].dist+=p[i-1].dist;
    }
    for(int i=h[u];~i;i=ne[i]) calc(e[i]);//递归u的每颗子树
}

LL query(int u,int l,int r)
{
    LL res=0;
    for(auto &t:f[u])//枚举u的父节点
    {
        int g=age[t.u];
        if(g>=l&&g<=r) res+=t.dist;
        for(int i=0;i<3;i++)
        {
            if(i==t.num) continue;
            auto &p=son[t.u][i];
            if(p.empty()) continue;
            int a=lower_bound(p.begin(),p.end(),Son({l,-1}))-p.begin();//二分年龄>=L的最小值
            int b=lower_bound(p.begin(),p.end(),Son({r+1,-1}))-p.begin();//<=R的最大值
            res+=t.dist*(b-a)+p[b-1].dist-p[a-1].dist;
        }
    }
    for(int i=0;i<3;i++)
    {
        auto &p=son[u][i];
        if(p.empty()) continue;
        int a=lower_bound(p.begin(),p.end(),Son({l,-1}))-p.begin();
        int b=lower_bound(p.begin(),p.end(),Son({r+1,-1}))-p.begin();
        res+=p[b-1].dist-p[a-1].dist;
    }
    return res;
}

int main()
{
    scanf("%d%d%d", &n, &m,&A);
    for(int i=1;i<=n;i++) scanf("%d", &age[i]);
    memset(h, -1, sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    calc(1);
    LL res=0;
    while (m -- )
    {
        int u,a,b;
        scanf("%d%d%d", &u, &a,&b);
        int l=(a+res)%A,r=(b+res)%A;
        if(l>r) swap(l,r);
        res=query(u,l,r);
        printf("%lld\n",res);
    }
    return 0;
}