【HNOI 2015】开店 / 题解

【HNOI 2015】开店 / 题解

Description

风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。

很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 n 个地方,编号为 1 到 n,被 n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 i 个地方的妖怪年龄是 $x_i$​。妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 u(u 为编号),然后在 u 开一家面向年龄在 L 到 R 之间(即年龄大于等于 L、小于等于 R)的妖怪的店。也有可能 u 这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪,到点 u 的距离的和是多少(妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。

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

Simplified Description

给你一棵 $n$ 个点树,每个点都有一个权值。 有 $m$ 次询问,每次询问给你一个点,问这个点到所有权值在 $L$ 到 $R$ 之间 的点的距离和为多少。强制在线。

Idea

先将答案差分,考虑权值在 $[1,r]$ 内点到给定点的距离之和,可以用如下式子表示

$$\sum_{i=1}^r (dep_u+dep_i-2\times dep_{lca})=\sum_{i=1}^r dep_i+dep_u\times r+\sum dep_{lca}$$

发现除了 $\sum dep_{lca}$ 都挺好求的。

这时我们可以将点按照权值排序,然后依次插入。插入后它会给每个节点造成它自己深度的贡献,用树链剖分套线段树的区间操作即可。

因为我们需要询问在一段区间内的答案,因此需要将线段树可持久化。此时我们换用带修主席树维护。

时间复杂度 $\Theta(n\log^2n)$。

Code

#include <bits/stdc++.h>
#define N 200010
#define inf INT_MAX
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
int son[N],fa[N],siz[N],top[N],fv[N],num[N];
int cnt,head[N],id[N],rt[N],n,q,A;
ll sdep[N],dep[N],lastans;
ll read(){
	ll x=0,flag=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if (ch=='-') flag=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
	return x*flag;
}
struct Mon{
	int age,id;
	Mon(int a=0,int b=0){
		age=a,id=b;
	}
	bool operator < (const Mon &x) const{
		return age<x.age;
	}
}mon[N];
struct Node{
	int ls,rs,lazy;
	ll sum,esum;
}t[N<<7];
struct Edge{
	int to,next,val;
	Edge(int a=0,int b=0,int c=0){
		to=a,next=b,val=c;
	}
}l[N<<1];
void Add(int a,int b,int c){
	l[++cnt]=Edge(b,head[a],c);head[a]=cnt;
	l[++cnt]=Edge(a,head[b],c);head[b]=cnt;
}
void Pre_Work(int u,int f){
	fa[u]=f,siz[u]=1;
	int mx=-1;
	for (int i=head[u];i;i=l[i].next){
		int v=l[i].to;if (v==f) continue;
		dep[v]=dep[u]+l[i].val;fv[v]=l[i].val;
		Pre_Work(v,u);siz[u]+=siz[v];
		if (siz[v]>mx) mx=siz[v],son[u]=v;
	}
}
void Re_Build(int u,int topf){
	top[u]=topf,id[u]=++cnt;num[cnt]=fv[u];
	if (son[u]) Re_Build(son[u],topf);
	for (int i=head[u];i;i=l[i].next){
		int v=l[i].to;
		if (v!=son[u]&&v!=fa[u])
			Re_Build(v,v);
	}
}
void Build(int &p,int l,int r){
	int pre=p;p=++cnt;t[p]=t[pre];
	if (l==r) {t[p].esum=num[l];return;}
	Build(t[p].ls,l,mid);
	Build(t[p].rs,mid+1,r);
	t[p].esum=t[t[p].ls].esum+t[t[p].rs].esum;
}
void Update(int &p,int l,int r,int L,int R){
	int pre=p;p=++cnt;t[p]=t[pre];
	if (L<=l&&r<=R){
		++t[p].lazy;
		t[p].sum+=t[p].esum;
		return;
	}
	if (mid>=L) Update(t[p].ls,l,mid,L,R);
	if (mid<R) Update(t[p].rs,mid+1,r,L,R);
	t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum+t[p].esum*t[p].lazy;
}
ll Query(int p,int l,int r,int L,int R,int add){
	if (L<=l&&r<=R) return t[p].sum+t[p].esum*add;
	add+=t[p].lazy;
	if (mid>=R) return Query(t[p].ls,l,mid,L,R,add);
	if (mid<L) return Query(t[p].rs,mid+1,r,L,R,add);
	return Query(t[p].ls,l,mid,L,R,add)+Query(t[p].rs,mid+1,r,L,R,add);
}
ll Path_Query(int u,int ver){
	ll res=0;
	while(top[u]!=1){
		res+=Query(rt[ver],1,n,id[top[u]],id[u],0);
		u=fa[top[u]];
	}
	res+=Query(rt[ver],1,n,1,id[u],0);
	return res;
}
void Path_Update(int u,int ver){
	while(top[u]!=1){
		Update(rt[ver],1,n,id[top[u]],id[u]);
		u=fa[top[u]];
	}
	Update(rt[ver],1,n,1,id[u]);
}
ll Solve(int u,int ver){
	return sdep[ver]+dep[u]*ver-2*Path_Query(u,ver);
}
int main(){
	n=read(),q=read(),A=read();
	for (int i=1;i<=n;++i)
	mon[i].age=read(),mon[i].id=i;
	for (int i=2,a,b,c;i<=n;++i)
		a=read(),b=read(),c=read(),
		Add(a,b,c);cnt=0;
	Pre_Work(1,0);Re_Build(1,1);cnt=0;
	sort(mon+1,mon+1+n);
	Build(rt[0],1,n);
	for (int i=1;i<=n;++i)
		sdep[i]=sdep[i-1]+dep[mon[i].id],
		rt[i]=rt[i-1],Path_Update(mon[i].id,i);
	for (int i=1;i<=q;++i){
		int u;
		ll l,r;
		u=read(),l=read(),r=read();
		(l+=lastans)%=A,(r+=lastans)%=A;
		int L=min(l,r),R=max(l,r);
		l=lower_bound(mon+1,mon+1+n,Mon(L,0))-mon,
		r=upper_bound(mon+1,mon+1+n,Mon(R,inf))-mon-1;
		printf("%lld\n",lastans=Solve(u,r)-Solve(u,l-1));
	}
}
Show Comments