题面

 风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 $n$个地方，编号为 $1$ 到 $n$，被 $n-1$ 条带权的边连接起来。每个地方都住着一个妖怪，其中第$ i $个地方的妖怪年龄是 $x_i$。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于$ 3$。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 $18$ 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 $u$（$u$为编号），然后在 $u$开一家面向年龄在$ L$到$R$ 之间（即年龄大于等于 $L$、小于等于 $R$）的妖怪的店。也有可能 u这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 $L$ 到 $R$ 之间的妖怪，到点 $u$ 的距离的和是多少（妖怪到 $u$ 的距离是该妖怪所在地方到 $u$ 的路径上的边的权之和） ，幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。

简化题面

你有一棵树，每个点有点权，边有边权，每次询问点权在$[l,r]$之间的点到$x$的距离和。

思路

考虑如果只有一种点权怎么办，多次询问$x$，我们应该如何快速求出所有点到这个点的距离我们来看样例这张图，左边为点的序号，右边为点的点权。比如我们要让所有点权为$7$的点跑到$4$号点。那我们可以先求出每个点到一个固定根节点的距离，然后再加上根节点到$x$这个点的距离，并且要减去两倍这个点与$x$的$LCA$到根的距离，那么就是单个点到$x$的距离，让我们来考虑多个，这个$LCA$貌似不大好求，怎么办。我们可以整体求，让每个点子树中的询问点权点的个数*向上到父亲的那条边权，答案就是每个点到根节点的距离之和+该询问点权点的个数*x到根的距离-2*(每个点子树中的询问点权点的个数*向上到父亲的那条边权)${\color{red} 一直到根的和}$。然后考虑对于多种颜色，那么建立主席树把点权$sort$后维护每个点加入后的版本即可，用标记永久化维护每个点子树中的询问点权点的个数*向上到父亲的那条边权就可以完成此题啦。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL Maxn=150000+5;
LL root,n,Q,A,last[Maxn],lsh[Maxn],head[Maxn],dis[Maxn],seg[Maxn],top[Maxn],deep[Maxn],rev[Maxn],son[Maxn],size[Maxn],rt[Maxn],f[Maxn],sumlen[Maxn],tot=0,id=0,dist[Maxn],stot[Maxn];
struct node{LL a,b;friend bool operator < (node x, node y){return x.a!=y.a?x.a<y.a:x.b<y.b;}}x[Maxn];
struct edge{LL to,next,dis;}e[Maxn<<1];
struct tree{LL ls,rs;LL sum,add;}tree[10000010];
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void add(LL u,LL v,LL w){e[++id].next=head[u];e[id].to=v;e[id].dis=w;head[u]=id;}
inline void dfs1(LL u,LL fa)
{
	size[u]=1;f[u]=fa;
	for (LL i=head[u];i;i=e[i].next)
	{
		LL v=e[i].to;
		if (v==fa) continue;
		deep[v]=deep[u]+e[i].dis;
		dfs1(v,u);
		last[v]=e[i].dis;
		size[u]+=size[v];
		if (size[v]>size[son[u]]) son[u]=v;
	}
}
inline void dfs2(LL u,LL fa)
{
	if (son[u]){seg[son[u]]=++seg[0],sumlen[seg[son[u]]]=last[son[u]],rev[seg[0]]=son[u],top[son[u]]=top[u];dfs2(son[u],u);}
	for (LL i=head[u];i;i=e[i].next)
	{
		LL v=e[i].to;
		if (!top[v]&&v!=son[u]){top[v]=v,seg[v]=++seg[0],sumlen[seg[v]]=last[v],rev[seg[0]]=v;dfs2(v,u);}
	}
}
inline LL update(LL pre,LL l,LL r,LL ql,LL qr)
{
    LL root=++tot;
	LL mid=l+r>>1;
    tree[root]=tree[pre];
    if (l==ql&&r==qr) {tree[root].add++;return root;}
    tree[root].sum+=(sumlen[qr]-sumlen[ql-1]);
    if (qr<=mid) tree[root].ls=update(tree[root].ls,l,mid,ql,qr);
    if (ql>mid) tree[root].rs=update(tree[root].rs,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) tree[root].ls=update(tree[root].ls,l,mid,ql,mid),tree[root].rs=update(tree[root].rs,mid+1,r,mid+1,qr);
	return root;
}
inline LL insert(LL u)
{
	while (top[u]!=1){root=update(root,1,seg[0],seg[top[u]],seg[u]);u=f[top[u]];}
	root=update(root,1,seg[0],1,seg[u]);return root;
}
LL query(LL root,LL l,LL r,LL ql,LL qr)
{
    LL res=1LL*(sumlen[qr]-sumlen[ql-1])*tree[root].add;
    if (l==ql&&qr==r) {return res+tree[root].sum;}
    LL mid=l+r>>1;
    if (qr<=mid) return res+query(tree[root].ls,l,mid,ql,qr);
    if (ql>mid) return res+query(tree[root].rs,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) return res+query(tree[root].ls,l,mid,ql,mid)+query(tree[root].rs,mid+1,r,mid+1,qr);
}
LL ask(LL root,LL u)
{
    LL res=0;
    while (top[u]!=1){res+=query(root,1,seg[0],seg[top[u]],seg[u]);u=f[top[u]];}
    return res+query(root,1,seg[0],1,seg[u]);
}
int main()
{
	seg[0]=seg[1]=top[1]=rev[1]=1;
	read(n),read(Q),read(A);
	for (LL i=1;i<=n;i++) read(x[i].a),x[i].b=i;
	sort(x+1,x+n+1);
	for (LL a,b,c,i=1;i<n;i++)
	{
		read(a),read(b),read(c);
		add(a,b,c),add(b,a,c);
	}
	dfs1(1,1);
	dfs2(1,1);
	for (LL i=1;i<=n;i++) sumlen[i]+=sumlen[i-1],dist[i]=dist[i-1]+deep[x[i].b];
	for (LL i=1;i<=n;i++) rt[i]=insert(x[i].b);
	LL las=0;
	for (LL i=1;i<=Q;i++)
	{
		LL u,a,b,L,R;
		read(u),read(a),read(b);
		L=min((a+las)%A,(b+las)%A),R=max((a+las)%A,(b+las)%A);
		L=lower_bound(x+1,x+n+1,(node){L,0})-x;
		R=upper_bound(x+1,x+n+1,(node){R,1e9})-x-1;
		las=dist[R]-dist[L-1]+(R-L+1)*deep[u]-2*(ask(rt[R],u)-ask(rt[L-1],u));
		cout<<las<<endl;
	}
	return 0; 
}