loj的提交记录

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long //答案爆 int 了
const int N=1e5+5e4+10;
int n,m,A,tot=0,head[N],val[N];
struct edge{int nex,go,wt;}g[N<<1];
void add(int x,int y,int v) {
	g[++tot]=(edge){head[x],y,v};
	head[x]=tot;
}
int read() {
	int x=0,minus=0; char ch;
	while (!isdigit(ch=getchar())) minus|=(ch=='-');
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return minus?-x:x;
}
int max(int x,int y) {return x>y?x:y;}
int min(int x,int y) {return x<y?x:y;}
void swap(int &x,int &y) {int tmp=x; x=y; y=tmp;}
bool vis[N]; //vis 记录跑过的重心
int sum,rt,sz[N],dp[N]; //求重心用到的一些东西
void get_rt(int x,int f) { //得到重心
	sz[x]=1; dp[x]=0;
	for (int i=head[x];i;i=g[i].nex) {
		int y=g[i].go;
		if (y==f||vis[y]) continue;
		get_rt(y,x);
		sz[x]+=sz[y];
		dp[x]=max(dp[x],sz[y]);
	}
	dp[x]=max(dp[x],sum-sz[x]);
	if (dp[x]<dp[rt]) rt=x;
}
struct emt{int age,pos;};
//age 年龄  pos 节点标号
bool cmp(emt x,emt y) {return x.age<y.age;}
//以年龄为第一关键字排序
int dep[N],dis[N][19],fa[N];
//dep[x]为 x 节点在分治树的深度
// dis[x][i]为 x 节点 到 分治树上的深度为 dep[i] 的祖先(有且只有一个)的距离
// fa[x]为 x 节点在分治树的父亲
struct jgll {
	int Max; //Max=msg.size();
	std::vector<int >ans[2];
	//tr[x].ans[0] 储存分治树 x 节点及其子树到 x 节点的距离 
	//tr[x].ans[1] 储存分治树 x 节点及其子树到 fa[x] 节点的距离
	std::vector<emt >msg;
	//tr[x].msg 储存分治树 x 节点及其子树的信息(用于初始化 tr[x].ans)
	void start(int anc) {
		Max=msg.size();
		std::sort(msg.begin(),msg.end(),cmp); //按年龄排序，以后二分查找年龄
		for (int i=0;i<Max;++i) {
			int x=msg[i].pos;
			ans[0].push_back(dis[x][dep[anc]]);
			ans[1].push_back(dis[x][dep[fa[anc]]]); //储存距离
		}
		for (int i=1;i<Max;++i) ans[0][i]+=ans[0][i-1],ans[1][i]+=ans[1][i-1]; //求前缀
	}
	int get_sml(int x) { //得到序号最小的 age 且不小于 x,返回序号
		int l=0,r=Max-1,res=Max;
		while (l<=r) {
			int mid=(l+r)>>1;
			if (msg[mid].age<x) l=mid+1;
			else r=mid-1,res=mid;
		}
		return res;
	}
	int get_big(int x) { //得到序号最大的 age 且不大于 x ,返回序号
		int l=0,r=Max-1,res=-1;
		while (l<=r) {
			int mid=(l+r)>>1;
			if (msg[mid].age>x) r=mid-1;
			else l=mid+1,res=mid;
		}
		return res;
	}
	int get_ans(int d,int L,int R,int id) { //id 是判断是否到 fa[x] (0 不是 ，1 是)
		L=get_sml(L); R=get_big(R); 
		if (L>R) return 0;
		if (L==0) return d*(R+1)+ans[id][R]; //特判一下
		return d*(R-L+1)+ans[id][R]-ans[id][L-1]; //
	}
}tr[N];
void get_dis(int x,int f,int d,int anc) { //没什么特别的储存信息
	dis[x][dep[anc]]=d;
	tr[anc].msg.push_back((emt){val[x],x});
	for (int i=head[x];i;i=g[i].nex) {
		int y=g[i].go;
		if (y==f||vis[y]) continue;
		get_dis(y,x,d+g[i].wt,anc);
	}
}
void solve(int x,int f) { //没什么特别的点分治
	dep[x]=dep[f]+1; vis[x]=true;
	fa[x]=f; get_dis(x,f,0,x);
	for (int i=head[x];i;i=g[i].nex) {
		int y=g[i].go;
		if (vis[y]) continue;
		sum=sz[y]; rt=0;
		get_rt(y,x);  solve(rt,x);
	}
}
int work(int x,int L,int R,int res=0) { //从 x 暴力跑分治树
	int xx=x;
	res=tr[xx].get_ans(0,L,R,0); //先记录本身的贡献
	while (fa[x]) {
		int d=dis[xx][dep[fa[x]]]; //fa[x] 到 xx 距离
		res+=tr[fa[x]].get_ans(d,L,R,0); //计算fa[x]的贡献
		res-=tr[x].get_ans(d,L,R,1); //再减去 x 节点及其子树到fa[x]的贡献
		x=fa[x];
	}
	return res;
}
signed main() {
	//freopen("1.in","r",stdin);
	n=read(),m=read(),A=read();
	for (int i=1;i<=n;++i) val[i]=read()%A;
	for (int i=1;i<n;++i) {
		int x=read(),y=read(),v=read();
		add(x,y,v); add(y,x,v);
	}
	sum=dp[0]=n; rt=0;
	get_rt(1,0); solve(rt,0);
	for (int i=1;i<=n;++i) tr[i].start(i); //预处理
	int last=0;
	while (m--) {
		int x=read(),L=read(),R=read();
		L=(L+last)%A; R=(R+last)%A;
		if (L>R) swap(L,R);
		printf("%lld\n",last=work(x,L,R));
	}
	return 0;
}