【BZOJ4012】[HNOI2015]开店
Description
风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 n个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 u（u为编号），然后在 u开一家面向年龄在 L到R 之间（即年龄大于等于 L、小于等于 R）的妖怪的店。也有可能 u这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪，到点 u 的距离的和是多少（妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和） ，幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。
Input
第一行三个用空格分开的数 n、Q和A，表示树的大小、开店的方案个数和妖怪的年龄上限。
第二行n个用空格分开的数 x_1、x_2、…、x_n，x_i 表示第i 个地点妖怪的年龄，满足0<=x_i<A。(年龄是可以为 0的，例如刚出生的妖怪的年龄为 0。)
接下来 n-1 行，每行三个用空格分开的数 a、b、c，表示树上的顶点 a 和 b 之间有一条权为c(1 <= c <= 1000)的边，a和b 是顶点编号。
接下来Q行，每行三个用空格分开的数 u、 a、 b。对于这 Q行的每一行，用 a、b、A计算出 L和R，表示询问“在地方 u开店，面向妖怪的年龄区间为[L,R]的方案的方便值是多少”。对于其中第 1 行，L 和 R 的计算方法为：L=min(a%A,b%A), R=max(a%A,b%A)。对于第 2到第 Q行，假设前一行得到的方便值为 ans，那么当前行的 L 和 R 计算方法为： L=min((a+ans)%A,(b+ans)%A), R=max((a+ans)%A,(b+ans)%A)。
Output
对于每个方案，输出一行表示方便值。
Sample Input
10 10 10
0 0 7 2 1 4 7 7 7 9
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4
0 0 7 2 1 4 7 7 7 9
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4
Sample Output
1603
957
7161
9466
3232
5223
1879
1669
1282
0
957
7161
9466
3232
5223
1879
1669
1282
0
HINT
满足 n<=150000,Q<=200000。对于所有数据，满足 A<=10^9
题解：前置技能BZOJ3924。
本题与3924不同的是，本题没有修改，但是每个查询都有一个范围限制， 那么将前缀和改成vector，存储所有点的颜色，然后将vector排序，查询时在vector里二分即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#define ub(A,B) (upper_bound(s[A].begin(),s[A].end(),node(B,0,0))-s[A].begin()-1)
#define lb(A,B) (lower_bound(s[A].begin(),s[A].end(),node(B,0,0))-s[A].begin()-1)
using namespace std;
const int maxn=150010;
typedef long long ll;
int n,m,cnt,tot,mn,rt,L,R;
ll A,ans;
int v[maxn],to[maxn<<1],next[maxn<<1],head[maxn],fa[maxn],siz[maxn],pos[maxn],vis[maxn],Log[maxn];
ll val[maxn<<1],dep[maxn],md[20][maxn<<1];
struct node
{
int color;
ll s1,s2;
node () {}
node (int a,ll b,ll c) {color=a,s1=b,s2=c;}
bool operator < (const node &b) const
{
return color<b.color;
}
};
vector<node> s[maxn];
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x,int fa)
{
md[0][++pos[0]]=dep[x],pos[x]=pos[0];
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) dep[to[i]]=dep[x]+val[i],dfs(to[i],x),md[0][++pos[0]]=dep[x];
}
void getrt(int x,int fa)
{
int i,tmp=0;
siz[x]=1;
for(i=head[x];i!=-1;i=next[i]) if(to[i]!=fa&&!vis[to[i]])
getrt(to[i],x),siz[x]+=siz[to[i]],tmp=max(tmp,siz[to[i]]);
tmp=max(tmp,tot-siz[x]);
if(tmp<mn) mn=tmp,rt=x;
}
void solve(int x)
{
vis[x]=1;
for(int i=head[x];i!=-1;i=next[i]) if(!vis[to[i]])
tot=siz[to[i]],mn=1<<30,getrt(to[i],x),fa[rt]=x,solve(rt);
}
ll lca(int a,int b)
{
a=pos[a],b=pos[b];
if(a>b) swap(a,b);
int k=Log[b-a+1];
return min(md[k][a],md[k][b-(1<<k)+1]);
}
ll dis(int a,int b)
{
return dep[a]+dep[b]-2*lca(a,b);
}
void updata(int x,int y)
{
ll d=0;
if(fa[x]) d=dis(fa[x],y);
node tmp(v[y],dis(x,y),d);
s[x].push_back(tmp);
if(fa[x]) updata(fa[x],y);
}
ll getdis(int x,int y)
{
ll ret=s[x][ub(x,R)].s1-s[x][lb(x,L)].s1;
int f=fa[x];
if(f) ret+=getdis(f,y)+((ub(f,R)-lb(f,L))-(ub(x,R)-lb(x,L)))*dis(f,y)-(s[x][ub(x,R)].s2-s[x][lb(x,L)].s2);
return ret;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd(),A=rd();
int i,j,u,a,b,c;
for(i=1;i<=n;i++) v[i]=rd();
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);
dfs(1,0);
for(i=2;i<=2*n-1;i++) Log[i]=Log[i>>1]+1;
for(j=1;(1<<j)<=2*n-1;j++) for(i=1;i+(1<<j)-1<=2*n-1;i++)
md[j][i]=min(md[j-1][i],md[j-1][i+(1<<(j-1))]);
tot=n,mn=1<<30,getrt(1,0),solve(rt);
for(i=1;i<=n;i++) updata(i,i);
for(i=1;i<=n;i++)
{
node t1(-1,0,0),t2(1<<30,0,0);
s[i].push_back(t1),s[i].push_back(t2);
sort(s[i].begin(),s[i].end());
for(j=1;j<(int)s[i].size();j++) s[i][j].s1+=s[i][j-1].s1,s[i][j].s2+=s[i][j-1].s2;
}
for(i=1;i<=m;i++)
{
u=rd(),a=rd(),b=rd(),L=min((a+ans)%A,(b+ans)%A),R=max((a+ans)%A,(b+ans)%A);
ans=getdis(u,u);
printf("%lld\n",ans);
}
return 0;
}//10 10 10 0 0 7 2 1 4 7 7 7 9 1 2 270 2 3 217 1 4 326 2 5 361 4 6 116 3 7 38 1 8 800 6 9 210 7 10 278 8 9 8 2 8 0 9 3 1 8 0 8 4 2 7 9 7 3 4 7 0 2 2 7 3 2 1 2 3 4
//10 1 10 0 0 7 2 1 4 7 7 7 9 1 2 270 2 3 217 1 4 326 2 5 361 4 6 116 3 7 38 1 8 800 6 9 210 7 10 278 2 1 3