「题解」「HNOI2015」开店 shop

HNOI2015 Day2 T2，一道动态点分治板子题。

题目链接：HNOI2015 Day2 T2、Luogu P3241、LOJ 2116、BZOJ 4012。

题目

风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。

这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 \(n\) 个地方，编号为 \(1\) 到 \(n\) 被 \(n-1\) 条带权的边连接起来。每个地方都住着一个妖怪，其中第 \(i\) 个地方的妖怪年龄是 \(x _ i\)。

妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 \(3\)。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 \(18\) 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 \(u\)（\(u\) 为编号），然后在 \(u\) 开一家面向年龄在 \(L\) 到 \(R\) 之间（即年龄大于等于 \(L\) 小于等于 \(R\)）的妖怪的店。

也有可能 \(u\) 这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 \(L\) 到 \(R\) 之间的妖怪，到点 \(u\) 的距离的和是多少（妖怪到 \(u\) 的距离是该妖怪所在地方到 \(u\) 的路径上的边的权之和），幽香把这个称为这个开店方案的方便值。

幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。

数据范围

时空限制

题解

思路

动态点分治板子题。主要是卡常数。

1. 快读必须加上；
2. 存图用 \(\texttt{vector}\)，这是 cache friendly 的。
3. 尽量少调用函数，函数传参，参数不变时改成全局变量。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1.5e5+5;
const int MAXQ=2e5+5;
const int inf=0x3f3f3f3f;

int n,Q,A;
int x[MAXN];

namespace Tree{
	struct Edge{
		int to,w;
		inline Edge(reg int to=0,reg int w=0):to(to),w(w){
			return;
		}
	};
	vector<Edge> G[MAXN];
	inline void Add_Edge(reg int u,reg int v,reg int len){
		G[u].push_back(Edge(v,len));
		return;
	}
	struct Nodef{
		int id,fa,dis;
		inline Nodef(reg int id=0,reg int fa=0,reg int dis=0):id(id),fa(fa),dis(dis){
			return;
		}
	};
	struct Nodes{
		int age,cnt;
		ll dis;
		inline Nodes(reg int age=0,reg int cnt=0,reg ll dis=0):age(age),cnt(cnt),dis(dis){
			return;
		}
		inline bool operator<(const Nodes& a)const{
			return age<a.age;
		}
	};
	vector<Nodef> fa[MAXN];
	vector<Nodes> son[MAXN][3];
	bitset<MAXN> del;
	int root,MaxPart;
	int size[MAXN];
	int _tot;
	inline void DFS1(reg int u,reg int father){
		size[u]=1;
		int Max=0;
		for(auto E:G[u]){
			reg int v=E.to;
			if(v!=father&&!del[v]){
				DFS1(v,u);
				size[u]+=size[v];
				Max=max(Max,size[v]);
			}
		}
		Max=max(Max,_tot-size[u]);
		if(Max<MaxPart)
			root=u,MaxPart=Max;
		return;
	}
	int dis[MAXN];
	int _id;
	inline void DFS2(reg int u,reg int father){
		fa[u].push_back(Nodef(_id,root,dis[u]));
		son[root][_id].push_back(Nodes(x[u],1,dis[u]));
		for(auto E:G[u]){
			reg int v=E.to,w=E.w;
			if(v!=father&&!del[v]){
				dis[v]=dis[u]+w;
				DFS2(v,u);
			}
		}
		return;
	}
	inline void solve(reg int u,reg int tot){
		if(tot==1){
			del[u]=true;
			fa[u].push_back(Nodef(-1,u,0));
			return;
		}
		MaxPart=inf;
		_tot=tot;
		DFS1(u,0);
		del[root]=true;
		fa[root].push_back(Nodef(-1,root,0));
		reg int id=0;
		for(auto E:G[root]){
			reg int v=E.to,w=E.w;
			if(del[v])
				continue;
			dis[v]=w;
			_id=id;
			DFS2(v,0);
			son[root][id].push_back(Nodes(inf,0,0));
			sort(son[root][id].begin(),son[root][id].end());
			for(reg int j=son[root][id].size()-2;j>=0;--j){
				son[root][id][j].cnt+=son[root][id][j+1].cnt;
				son[root][id][j].dis+=son[root][id][j+1].dis;
			}
			++id;
		}
		for(auto E:G[root]){
			reg int v=E.to;
			if(!del[v])
				solve(v,size[v]);
		}
		return;
	}
	inline ll query(reg int l,reg int r,reg int u){
		reg ll res=0;
		static vector<Nodes>::iterator L,R;
		for(reg int i=fa[u].size()-1;i>=0;--i){
			reg int f=fa[u][i].fa;
			for(reg int id=0;id<3;++id){
				if(id==fa[u][i].id||son[f][id].empty())
					continue;
				L=lower_bound(son[f][id].begin(),son[f][id].end(),Nodes(l,0,0));
				R=upper_bound(son[f][id].begin(),son[f][id].end(),Nodes(r,0,0));
				res+=1ll*fa[u][i].dis*(L->cnt-R->cnt)+L->dis-R->dis;
			}
			if(l<=x[f]&&x[f]<=r)
				res+=fa[u][i].dis;
		}
		return res;
	}
}

int main(void){
	n=read(),Q=read(),A=read();
	for(reg int i=1;i<=n;++i)
		x[i]=read();
	for(reg int i=1;i<n;++i){
		static int a,b,c;
		a=read(),b=read(),c=read();
		Tree::Add_Edge(a,b,c);
		Tree::Add_Edge(b,a,c);
	}
	Tree::solve(1,n);
	reg ll lastans=0;
	for(reg int i=1;i<=Q;++i){
		static int u;
		static ll a,b;
		u=read(),a=read(),b=read();
		a=(a+lastans)%A,b=(b+lastans)%A;
		if(a>b)
			swap(a,b);
		printf("%lld\n",lastans=Tree::query(a,b,u));
	}
	return 0;
}