TJ - 「HNOI2015」开店（洛谷）
一，题意
给你一棵\(n\)个节点的树，点有点权，边有边权，\(Q\)次询问每次让你求解点权在\(L\)到\(R\)之间的点到点\(u\)的距离和。（强制在线）
数据范围：\(n\le 1.5\times10^5,Q\le2\times10^5\)
二，思路
首先，我们先看弱化版，假设没有年龄的限制，看单个询问，设\(dis_i\)表示点\(i\)到根节点的路径上的和。题目就是求：
\[\sum_{i=l}^rdis_i+dis_u-2\times dis_{lca(i,u)}前面两项好求，关键是我们如何求解出$dis_{lca(i,u)}$呢？ \]其实我们发现，\(lca(i,u)\)到根节点的路径其实就是\(i,u\)到根节点的路径的重合的部分。
那么，我们考虑先将\(i\in[l,r]\)到根节点的路径上的边打上一个标记，（每个\(i\)都给其经过的边每条的标记+1），最后再让\(u\)往根节点走，\(dis_{lca(i,u)}\)就是路径上每个边的标记数量乘上此边权的和。
其实这个过程可以用树链剖分来解决。
但是呢，由于有年龄限制，我们可以将线段树改为主席树，在按照年龄对\(n\)个点排序后，每个点都开一新的，每次答案做差即可。
不过由于有多个区间修改，空间可能会爆炸，我们需要搞一个标记永久化。
请注意代码细节。
三，代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=15e4+5;
int n,Q;
ll A;
vector<int> V;//用来对年龄进行离散化
inline int get_id(int x){
return lower_bound(V.begin(),V.end(),x)-V.begin()+1;
}
//建图：
struct edge{
int v,nt;
ll w;
}a[N*2];
int head[N],at;
inline void add(int u,int v,ll w){
a[++at].v=v,a[at].nt=head[u],head[u]=at,a[at].w=w;
}
struct node{
int val;
int id;
}age[N];//年龄 (点权)
ll dis[N];//点i到根节点的路径上的权值和
ll val[N],sum[N];//第i个点的父亲边的边权 ,dis数组排序后的前缀和
bool cmp(node x,node y){
return x.val<y.val;
}
//第一次dfs求解的树剖的东西：
int son[N],deep[N],fa[N],siz[N];
void dfs1(int u,int dad){
deep[u]=deep[dad]+1,fa[u]=dad,siz[u]=1;
int v;
ll w;
for(int i=head[u];i;i=a[i].nt){
v=a[i].v,w=a[i].w;
if(v==dad) continue;
dis[v]=dis[u]+w,val[v]=w;
dfs1(v,u);
if(siz[son[u]]<siz[v]) son[u]=v;
siz[u]+=siz[v];
}
}
//第二次dfs求解的树剖的东西：
int id[N],rev[N],top[N],dfn;
void dfs2(int u){
id[u]=++dfn,rev[dfn]=u;
if(son[u]){
top[son[u]]=top[u];
dfs2(son[u]);
}
int v;
for(int i=head[u];i;i=a[i].nt){
v=a[i].v;
if(id[v]) continue;
top[v]=v;
dfs2(v);
}
}
//主席树：
int root[N],tot=0;
struct Segment_tree{
int l,r;
ll sum,lazy,ans;//sum表示这个区间内本来的边权和，lazy为永久化标记，ans为区间的和
}tree[N*52];
int build(int l,int r){
int p=++tot;
if(l==r){
tree[p].sum=val[rev[l]];
return p;
}
int mid=(l+r)>>1;
tree[p].l=build(l,mid);
tree[p].r=build(mid+1,r);
tree[p].sum=tree[tree[p].l].sum+tree[tree[p].r].sum;
return p;
}
int insert(int pre,int l,int r,int x,int y){
int p=++tot;
tree[p]=tree[pre];
if(x<=l&&r<=y){
tree[p].lazy++;
tree[p].ans+=tree[p].sum;
return p;
}
int mid=(l+r)>>1;
if(x<=mid) tree[p].l=insert(tree[pre].l,l,mid,x,y);
if(y>=mid+1) tree[p].r=insert(tree[pre].r,mid+1,r,x,y);
tree[p].ans=tree[tree[p].l].ans+tree[tree[p].r].ans+tree[p].sum*tree[p].lazy;
return p;
}
ll query(int p,int l,int r,int x,int y,ll add){
if(x<=l&&r<=y) return tree[p].ans+tree[p].sum*add;
int mid=(l+r)>>1;
ll ans=0;
add+=tree[p].lazy;
if(x<=mid) ans+=query(tree[p].l,l,mid,x,y,add);
if(y>=mid+1) ans+=query(tree[p].r,mid+1,r,x,y,add);
return ans;
}
inline ll ask(int u,ll r){
ll ans=sum[r]+r*dis[u],tmp=0;
int x=u;
int fx=top[x];
while(fx!=1){
tmp+=query(root[r],1,n,id[fx],id[x],0);
x=fa[fx];
fx=top[x];
}
tmp+=query(root[r],1,n,id[1],id[x],0);
return ans-tmp*2;
}
int main(){
//读入:
scanf("%d%d%lld",&n,&Q,&A);
for(int i=1;i<=n;i++){
scanf("%d",&age[i].val);
V.push_back(age[i].val);
age[i].id=i;
}
int u,v,w;
for(int i=1;i<n;i++){
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
//树链剖分：
dfs1(1,0);
top[1]=1;
dfs2(1);
//预处理离散化等:
sort(V.begin(),V.end());
sort(age+1,age+1+n,cmp);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+dis[age[i].id];
//建立主席树:
root[0]=build(1,n);
int x,fx;
for(int i=1;i<=n;i++){
root[i]=root[i-1];
x=age[i].id,fx=top[x];
while(fx!=1){
root[i]=insert(root[i],1,n,id[fx],id[x]);
x=fa[fx];
fx=top[x];
}
root[i]=insert(root[i],1,n,id[1],id[x]);
}
//求解：
ll ans=0,aa,bb,l,r;
while(Q--){
scanf("%d%lld%lld",&u,&aa,&bb);
l=min((aa+ans)%A,(bb+ans)%A);
r=max((aa+ans)%A,(bb+ans)%A);
l=lower_bound(V.begin(),V.end(),l)-V.begin()+1;
r=upper_bound(V.begin(),V.end(),r)-V.begin();
ans=ask(u,r);
if(l>1) ans-=ask(u,l-1);
printf("%lld\n",ans);
}
return 0;
}