记录编号	365917	评测结果	AAAAAAAAAA
题目名称	[HNOI 2015]开店	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	20.337 s
提交时间	2017-01-22 07:23:51	内存使用	19.36 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 150005, maxd = 20;
struct Edge {
	int next, to, dis;
	Edge(int a=0, int b=0, int c=0) :
		next(a), to(b), dis(c) {}
} e[maxn<<1];
int head[maxn], tot;
void Add(int u, int v, int w) {
	e[++tot] = Edge(head[u], v, w); head[u] = tot;
}
int N, Q, A, age[maxn];
int size[maxn], vis[maxn], root, Size, F;
int dis[maxn][maxd], fa[maxn], res[maxn], sub[maxn][maxd];
struct Node {
	ll d;int g;
	Node(int a=0, int b=0) : d(a), g(b){}
	bool operator < (const Node& x) const {
		return g < x.g;
	}
};
vector<Node> vt[maxn], vtt[maxn][maxd];
void print(vector<Node>& v) {
	for(int i=0; i<(int)v.size(); ++i)
		printf("(%d,%d)", v[i].d, v[i].g); puts("");
}
int search(vector<Node>&v, int p) {
	int l = 0, r = v.size()-1, mid, ans = -1;
	while(l<=r) {
		mid = (l+r)>>1;
		if(v[mid].g<=p) ans = mid, l = mid+1;
		else r = mid-1;
	}
	return ans;
}
ll solve(vector<Node>&v, int l, int r, int d) {
	int ri = search(v, r), le = search(v, l-1);
	// print(v);
	// printf("%d], %d] \n", le, ri);
	if(ri<0) return 0;
	if(le>=0) return 1LL*(v[ri].d-v[le].d)+1LL*(ri-le)*d;
	else return 1LL*v[ri].d+1LL*(ri+1)*d;
}
ll query(int x, int l, int r) {
	// printf("query %d %d %d\n", x, l, r);
	ll ans = solve(vt[x], l, r, 0); 
	// printf("%lld ans <<\n", ans);
	for(int y=fa[x], rs=res[x]-1; y; y=fa[y], --rs) {
		// printf("x %d fa %d res %d sub %d dis %d\n", x, y, rs, sub[x][rs], dis[x][rs]);
		ans += solve(vt[y], l, r, dis[x][rs]);
		// printf(">>> %d\n", solve(vt[y], l, r, dis[x][rs]));
		ans -= solve(vtt[sub[x][rs]][rs], l, r, dis[x][rs]);
		// printf(">>> %d\n", solve(vtt[sub[x][rs]][rs], l, r, dis[x][rs]));
		// printf("%lld ans <<\n", ans);
	}
	return ans;
}
void getdep(int x, int fa, int Sub, int Rt) {
	int r = res[Rt];
	sub[x][r] = Sub; //printf("%d %d %d %d\n", Rt, r, x, Sub);
	vt[Rt].push_back(Node(dis[x][r], age[x]));
	vtt[Sub][r].push_back(Node(dis[x][r], age[x]));
	// printf("%d %d\n", x, fa); print(vt[Rt]);
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		dis[to][r] = dis[x][r]+e[i].dis;
		getdep(to, x, Sub, Rt);
	}
}
void sumup(vector<Node>& v) {
	sort(v.begin(), v.end());
	// print(v);
	for(int i=1; i<(int)v.size(); ++i)
		v[i].d += v[i-1].d;
}
void build(int x) {
	int r = res[x];
	vt[x].push_back(Node(0, age[x]));
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		dis[to][r] = e[i].dis;
		getdep(to, x, to, x);
		sumup(vtt[to][r]);
	}
	// puts("VT");
	sumup(vt[x]);
}
int getroot(int x, int fa) {
	int f = 0; size[x] = 1;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		size[x] += getroot(to, x);
		f = max(f, size[to]);
	} 
	f = max(f, Size-size[x]);
	if(f<=F) F = f, root = x;
	return size[x];
}
void Build(int x) {
	// printf("------------%d-%d--------\n", x, res[x]);
	vis[x] = 1; build(x);
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		F = Size = size[to]; getroot(to, x);
		fa[root] = x;
		res[root] = res[x]+1;
		Build(root);
	}
}
int main() {	
	freopen("shop_hnoi2015.in","r",stdin);
	freopen("shop_hnoi2015.out","w",stdout);
	scanf("%d%d%d", &N, &Q, &A);
	for(int i=1; i<=N; ++i) scanf("%d", age+i);
	for(int i=1,a,b,c; i<N; ++i) {
		scanf("%d%d%d", &a, &b, &c);
		Add(a, b, c); Add(b, a, c);
	}
	F = Size = N; getroot(1, -1);
	res[root] = 1; Build(root);
	ll ans = 0;
	for(int i=1,x,a,b,l,r; i<=Q; ++i) {
		scanf("%d%d%d", &x, &a, &b);
		l = min((a+ans)%A, (b+ans)%A);
		r = max((a+ans)%A, (b+ans)%A);
		ans = query(x, l, r);
		printf("%lld\n", ans);
	}
	return 0;
}