Description：

一棵树上每个点有一个值 $v$ ，每次询问树上所有 $v$ 在 $[l,r]$ 内的点到这个点的距离之和。

$1\le n \le 150000$

Solution：

动态点分治，还是维护 $sum,tofa,tot$ ，但是由于有区间询问，所以每个点记一个 $vector$ ，把 $vector$ 中的元素按 $v$ 排序，做一个后缀和，之所以是后缀和是因为可以在后面 $push\_back$ 一个极大值 $upper\_bound$ 不会出问题，然后每次在 $vector$ 里二分一下就取得了想要的范围，二分可以用 $STL$ 的 $lower\_bound$ 和 $upper\_bound$ ，注意 $upper\_bound$ 中 $pair$ 的第二个元素应设为无穷大，然后就是卡常了，首先每次不能二分八次，然后 $LCA$ 用 $ST$ 表求。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<vector>

#include<cstring>

using namespace std;

#define min(a,b) ((a)<(b)?(a):(b))

int n,maxy,m;

#define MAXN 150010

#define INF 0x3f3f3f3f

#define INFLL 999999999999ll

typedef long long ll;

int val[MAXN];

int w[MAXN];

bool cmp(int x,int y){return val[x] < val[y];}

struct edge

{

	int to,nxt;

	ll v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,ll c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

ll len[MAXN];

int rank[MAXN];

int cur = 0;

ll f[MAXN << 2][20];

void dfs(int k,int fa)

{

	f[++cur][0] = len[k];rank[k] = cur;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		len[e[i].to] = len[k] + e[i].v;

		dfs(e[i].to,k);

		f[++cur][0] = len[k];

	}

	return;

}

inline void ST()

{

	for(register int k = 1;k <= 19;++k)

		for(register int i = 1;i <= cur;++i)

			f[i][k] = min(f[i][k - 1],f[i + (1 << (k - 1))][k - 1]);

	return;

}

inline ll dis(int a,int b)

{

	if(rank[a] > rank[b])swap(a,b);

	register int k = log2(rank[b] - rank[a] + 1);

	return len[a] + len[b] - 2 * min(f[rank[a]][k],f[rank[b] - (1 << k) + 1][k]);

}

int root,d[MAXN],size[MAXN],anc[MAXN],s;

bool v[MAXN];

void getroot(int k,int fa)

{

	d[k] = 0;size[k] = 1;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

		size[k] += size[e[i].to];

		if(size[e[i].to] > d[k])

		{

			d[k] = size[e[i].to];

		}

	}

	d[k] = max(d[k],s - size[k]);

	if(d[k] < d[root])root = k;

	return;

}

void divide(int k)

{

	v[k] = true;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		s = size[e[i].to];root = 0;

		getroot(e[i].to,0);

		anc[root] = k;

		divide(root);

	}

	return;

}

vector< pair<int,ll> > sum[MAXN],tofa[MAXN],tot[MAXN];

#define fi first

#define se second

inline void modify(int p,int v)

{

	tot[p].push_back(make_pair(v,1ll));

	sum[p].push_back(make_pair(v,0ll));

	for(register int i = p;anc[i] != 0;i = anc[i])

	{

		sum[anc[i]].push_back(make_pair(v,dis(p,anc[i])));

		tofa[i].push_back(make_pair(v,dis(p,anc[i])));

		tot[anc[i]].push_back(make_pair(v,1ll));

	}

	return;

}

inline void maintain(int k)

{

	tot[k].push_back(make_pair(maxy + 1,0));

	for(register int i = tot[k].size() - 3;i >= 0;--i)tot[k][i].se += tot[k][i + 1].se;

	sum[k].push_back(make_pair(maxy + 1,0));

	for(register int i = sum[k].size() - 3;i >= 0;--i)sum[k][i].se += sum[k][i + 1].se;

	tofa[k].push_back(make_pair(maxy + 1,0));

	for(register int i = tofa[k].size() - 3;i >= 0;--i)tofa[k][i].se += tofa[k][i + 1].se;

	return;

}

inline ll query(int k,int l,int r)

{

	register int L,R;

	L = lower_bound(sum[k].begin(),sum[k].end(),make_pair(l,0ll)) - sum[k].begin();

	R = upper_bound(sum[k].begin(),sum[k].end(),make_pair(r,INFLL)) - sum[k].begin();

	register ll res = sum[k][L].se - sum[k][R].se;

	for(register int i = k;anc[i] != 0;i = anc[i])

	{

		register ll d = dis(k,anc[i]);

		L = lower_bound(sum[anc[i]].begin(),sum[anc[i]].end(),make_pair(l,0ll)) - sum[anc[i]].begin();

		R = upper_bound(sum[anc[i]].begin(),sum[anc[i]].end(),make_pair(r,INFLL)) - sum[anc[i]].begin();

		res = res + (sum[anc[i]][L].se - sum[anc[i]][R].se) + (tot[anc[i]][L].se - tot[anc[i]][R].se) * d;

		L = lower_bound(tofa[i].begin(),tofa[i].end(),make_pair(l,0ll)) - tofa[i].begin();

		R = upper_bound(tofa[i].begin(),tofa[i].end(),make_pair(r,INFLL)) - tofa[i].begin();

		res = res - (tofa[i][L].se - tofa[i][R].se) - (tot[i][L].se - tot[i][R].se) * d;

	}

	return res;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	n = read();m = read();maxy = read();

	for(register int i = 1;i <= n;++i)val[i] = read();

	register int a,b,c;

	for(register int i = 1;i < n;++i)

	{

		a = read();b = read();c = read();

		add(a,b,c);

	}

	dfs(1,0);ST();

	root = 0;d[0] = INF;s = n;

	getroot(1,0);

	divide(root);

	for(register int i = 1;i <= n;++i)w[i] = i;

	sort(w + 1,w + 1 + n,cmp);

	for(register int i = 1;i <= n;++i)modify(w[i],val[w[i]]); 

	for(register int i = 1;i <= n;++i)maintain(i);

	register ll lastans = 0;

	register int u,x,y;

	for(register int i = 1;i <= m;++i)

	{

		u = read();a = read();b = read();

		x = min((a + lastans) % maxy,(b + lastans) % maxy);

		y = max((a + lastans) % maxy,(b + lastans) % maxy);

		lastans = query(u,x,y);

		printf("%lld\n",lastans);

	}

	return 0;

}