【LuoguP3241】[HNOI2015] 開店

題目連結

題意

給出一棵邊帶權的樹，多次線上詢問一個點到一個區間内的點的距離和。

Sol

分塊過不了的

一個 trick ，都知道要算兩點之間距離可以拆成到根的距離和他們的 LCA 到根的距離 ，其實要算多個點到一個點距離也可以使用一個類似的 trick。

問題就在于快速求解所有的： ∑ v ∈ S d e e p [ L C A ( u , v ) ] \sum_{v\in S}deep[LCA(u,v)] v∈S∑​deep[LCA(u,v)]

我們對于要詢問的點集 S S S ，每一個點向上把所有反祖的邊都覆寫一次，然後對于 u u u 點我們把它拿着一步步向上走，對于每一條經過的邊把它被覆寫的次數與這條邊的邊權的積求和，最後就是上面那個式子了。

也就是說現在我們的問題是快速求出一個區間内所有點向上覆寫後某一個點向上的每條邊被覆寫的次數與邊權的積。

這個顯然就用 主席樹+樹鍊剖分 來維護一下就可以了。

把點按順序插入，每一個點在樹上用樹剖往上，每一段在内層線段樹中進行修改。

不過這裡是區間修改，直接打可下放标記可能會很傷空間 ，那麼可以用标記永久化。

但是我們這裡是區間詢問，那麼就要用到一些巧妙的方法。

這個方法也可以用于二維線段樹等一般隻适用于單點查詢的問題。

觀察我們的詢問方式，先把我們要詢問的區間分為 l o g log log 個區間，然後當目前區間被完全覆寫的時候我們為了保證複雜度肯定不能繼續往下了，這樣如果我們使用正常的标記永久化的話我們就有可能沒辦法計算到下面的點的答案了。

這樣子我們就還需要維護一個标記，表示目前區間總修改量，即使目前區間沒有被修改完全修改我們也要更新這個标記。

這樣當我們查詢到一個被詢問區間完全覆寫的區間的時候我們就直接把目前區間的總修改量加上就可以了，因為我們隻有當詢問完全覆寫目前區間的時候才會用到這個标記，而這個标記相當于是把下面的修改資訊都上傳了之後的資訊，就沒有問題了。

code:

#include<bits/stdc++.h>
using namespace std;
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-')t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}
const int N=1.5e5+10;
int n,m,tp,RT;
typedef long long ll;
int dep[N],fa[N];ll dis[N];
struct edge{
	int to,next,w;
}a[N<<1];
int LIM;int head[N],cnt=0;
inline void add(int x,int y,int z){a[++cnt]=(edge){y,head[x],z};head[x]=cnt;}
int id[N],dfn[N],size[N],top[N],son[N],I=0,Ret[N];
namespace LISAN{
	int age[N],id[N];
	inline bool cmp(int i,int j){return age[i]<age[j];}
	inline int Lower(register int x){
		register int l=1,r=n,pos=n+1;
		while(l<=r){
			register int mid=l+r>>1;
			if(age[id[mid]]>=x) pos=mid,r=mid-1;else l=mid+1;
		}
		return pos;
	}
	void Prepare(){for(int i=1;i<=n;++i) id[i]=i,init(age[i]);sort(id+1,id+1+n,cmp);return;}
}using LISAN::Lower;
void Dfs(int u){
	size[u]=1;
	for(int v,i=head[u];i;i=a[i].next){
		v=a[i].to;if(v==fa[u]) continue;
		fa[v]=u,dep[v]=dep[u]+1;dis[v]=dis[u]+a[i].w;
		Ret[v]=a[i].w;Dfs(v);size[u]+=size[v];
		if(!son[u]||size[v]>size[son[u]]) son[u]=v;
	}
	return;
}
void dfs(int u,int t){
	top[u]=t;id[u]=++I,dfn[I]=u;
	if(!son[u]) return;
	dfs(son[u],t);
	for(int v,i=head[u];i;i=a[i].next) if((v=a[i].to)==son[u]||v==fa[u]) continue;else dfs(v,v);
	return;
}
ll Sum[N],SR[N];
const int MAXN=N*100;
int ls[MAXN],rs[MAXN],vis[MAXN],rt[N];
ll E[MAXN];int F[MAXN];int cur=0,NOW=0;
void Build(int &u,int l,int r){
	u=++cur;E[u]=F[u]=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	Build(ls[u],l,mid);Build(rs[u],mid+1,r);
	return;
}
void Modify(int&u,int l,int r,int L,int R){
	if(L>R) return;
	int p=u;
	if(vis[p]!=NOW) {p=++cur;
		ls[p]=ls[u],rs[p]=rs[u];
		E[p]=E[u],F[p]=F[u];vis[p]=NOW;
		u=p;
	}E[p]+=SR[R]-SR[L-1];
	if(l>=L&&r<=R) {++F[p];return;}
	int mid=l+r>>1;
	if(mid>=R) return Modify(ls[p],l,mid,L,R);
	if(mid< L) return Modify(rs[p],mid+1,r,L,R);
	Modify(ls[p],l,mid,L,mid);Modify(rs[p],mid+1,r,mid+1,R);
	return;
}

inline void Modify(int &rt,int u){
	++NOW;
	while(top[u]) {Modify(rt,1,n,id[top[u]],id[u]);u=fa[top[u]];}
	return;
}
void Query(int v,int u,int l,int r,int L,int R,ll&ans){
	if(L>R) return;
	if(!u&&!v) return;
	if(l>=L&&r<=R) {ans+=E[u]-E[v];return;}
	ans+=(SR[R]-SR[L-1])*(F[u]-F[v]);
	int mid=l+r>>1;
	if(mid>=R) return Query(ls[v],ls[u],l,mid,L,R,ans);
	if(mid< L) return Query(rs[v],rs[u],mid+1,r,L,R,ans);
	return Query(ls[v],ls[u],l,mid,L,mid,ans),Query(rs[v],rs[u],mid+1,r,mid+1,R,ans);
}
inline ll Query(int l,int r,int u){
	ll res=0;
	while(top[u]) Query(rt[l],rt[r],1,n,id[top[u]],id[u],res),u=fa[top[u]];
	return res;
}
void work(){
	int lst=0;
	Dfs(1),dfs(1,1);
	for(int i=1;i<=n;++i) SR[i]=SR[i-1]+Ret[dfn[i]];
	Build(rt[0],1,n);
	for(int i=1;i<=n;++i) Sum[i]=Sum[i-1]+dis[LISAN::id[i]],rt[i]=rt[i-1],Modify(rt[i],LISAN::id[i]);
	for(int i=1;i<=m;++i) {
		int l,r,x;init(x),init(l),init(r);
		l=(l+lst)%LIM,r=(r+lst)%LIM;
		if(l>r) swap(l,r);
		l=Lower(l);r=Lower(r+1)-1;ll ans=0;
		ans=Query(l-1,r,x);
		ans=(Sum[r]-Sum[l-1])+(ll)(r-l+1)*dis[x]-(ans<<1);
		printf("%lld\n",ans);
		lst=ans%LIM;
	}
}
int main()
{
	init(n),init(m),init(LIM);
	LISAN::Prepare();
	int u,v,w;
	for(int i=1;i<n;++i) {init(u),init(v),init(w);add(u,v,w);add(v,u,w);}
	work();
	return 0;
}