跑到 LOJ 上测了一下。后面的点基本都是 6050ms-6110ms 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int Maxn=150000+5;
const int inf=1e9;
struct edge{
	int v,nx,w;
}e[Maxn<<1];
struct father{
	int u,num;ll dis;
};
struct son{
	int val;ll dis;
	bool operator < (const son&t) const{
		return val<t.val;
	}
};
int n,m,A,ne,f[Maxn],val[Maxn];
bool vis[Maxn];
ll ans;
vector<father>fa[Maxn];
vector<son>s[Maxn][3];
inline int read()        
{	int s=0,f=1;        
	char ch=getchar();        
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}        
	while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}        
	return s*f;        
}
inline void read(int u,int v,int w)
{	e[++ne].v=v;
	e[ne].nx=f[u];
	e[ne].w=w;
	f[u]=ne;
}
inline int getsize(int u,int ffa)
{	if(vis[u])return 0;
	int res=1;
	for(int i=f[u];i;i=e[i].nx)
	{	int v=e[i].v;
		if(vis[v]||v==ffa)continue;
		res+=getsize(v,u);
	}
	return res;
}
inline int getrt(int u,int ffa,int sumn,int &rt)
{	if(vis[u])return 0;
	int sum=1,maxson=0;
	for(int i=f[u];i;i=e[i].nx)
	{	int v=e[i].v;
		if(v==ffa||vis[v])continue;
		int x=getrt(v,u,sumn,rt);
		maxson=max(maxson,x);
		sum+=x;
	}
	maxson=max(maxson,sumn-sum);
	if(maxson<=sumn/2)rt=u;
	return sum;
}
inline void getdis(int u,int ffa,ll dis,int rt,int k)
{	if(vis[u])return;
	fa[u].push_back(father{rt,k,dis});
	s[rt][k].push_back(son{val[u],dis});
	for(int i=f[u];i;i=e[i].nx)
	{	int v=e[i].v;
		if(v==ffa||vis[v])continue;
		getdis(v,u,dis+e[i].w,rt,k);
	}
}
inline void solve(int u)
{	if(vis[u])return;
	getrt(u,0,getsize(u,0),u);
	vis[u]=1;
	int k=0;//一个点的度数不超过 3  
	for(int i=f[u];i;i=e[i].nx,k++)
	{	int v=e[i].v;
		if(vis[v])continue;
		s[u][k].push_back(son{-1,0});
		s[u][k].push_back(son{A+1,0});//边界 
		getdis(v,0,e[i].w,u,k);
		sort(s[u][k].begin(),s[u][k].end());
		for(int i=1;i<s[u][k].size();i++)
			s[u][k][i].dis+=s[u][k][i-1].dis;
	}
	for(int i=f[u];i;i=e[i].nx)
		solve(e[i].v);
}
inline ll query(int u,int l,int r)
{	ll res=0;
	for(int i=0;i<fa[u].size();i++)
	{	father t=fa[u][i];
		int x=val[t.u];
		if(l<=x&&x<=r)res+=t.dis;
		for(int j=0;j<3;j++)
		{	if(j==t.num)continue;
			vector<son> p=s[t.u][j];
			if(p.empty())continue;
			int x=lower_bound(p.begin(),p.end(),son({l,-1}))-p.begin();
			int y=lower_bound(p.begin(),p.end(),son({r+1,-1}))-p.begin();
			res+=t.dis*(y-x)+p[y-1].dis-p[x-1].dis;
		}
	}
	for(int i=0;i<3;i++)
	{	vector<son> p=s[u][i];
		if(p.empty())continue;
		int x=lower_bound(p.begin(),p.end(),son({l,-1}))-p.begin();
		int y=lower_bound(p.begin(),p.end(),son({r+1,-1}))-p.begin();
		res+=p[y-1].dis-p[x-1].dis;
	}
	return res;
}
int main()
{	n=read();m=read();A=read();
	for(int i=1;i<=n;i++)val[i]=read();
	for(int i=1;i<n;i++)
	{	int u=read(),v=read(),w=read();
		read(u,v,w);read(v,u,w);
	}
	solve(1);
	while(m--)
	{	int u=read(),l=read(),r=read();
		l=(l+ans)%A;r=(r+ans)%A;
		if(l>r)swap(l,r);
		ans=query(u,l,r);
		printf("%lld\n",ans);
	}
	return 0;
}