【XSY1953】【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、 L,R\)。对于这 \(Q\)行的每一行,表示询问“在地方\(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


\(Sample Output\)

1603
957
7161
9466
3232
5223
1879
1669
1282
0


\(HINT\)

满足 \(n≤150000,Q≤200000\)。

对于所有数据,满足 \(A≤10^9\)


Source
练习题 树8-6-动态树分治


前置

正解:动态点分治

看到树上路径,我们考虑动态点分治做法

对于点分治还不了解的,请参考小张人大佬的博客

我们现在直接来讲动态点分治

动态点分治,实际上就是将点分治过程中,每个重心连在一起,建出一棵树,称为点分树

这个点分树有个十分利于暴力 有用的性质:树高保持在\(log_{n}\)层,于是我们就可以在点分树上暴力处理啦


本题思路

我们先将点分树建出来

然后从询问点\(ask\)在点分树内向上跳,直到根

在这条向上跳的路径上统计答案

对于统计答案的过程:

我们现在先考虑没有年龄限制的统计

我们用一张图来理解:
【XSY1953】【BZOJ4012】【HNOI2015】开店(动态点分治)
这是建出来的点分树,\(ask\)为\(3\)

假设现在遍历到的节点 \(x\) 为 \(1\),即以\(4\)为根的子树中的答案已经统计完了

那么现在没有统计答案的节点为\(1,2,6\)

我们可以发现,在计算路径时,\(1,2,6\)都要经过根节点\(1\),到达\(3\)

也就是说\(dis(1,3)\)要被计算三遍,也就是\(siz[1]-siz[4]\)遍(\(dis(a,b)\)表示\(a,b\)的距离)

所以我们先加上\(ans+=dis(1,3)\times(siz[1]-siz[4])\)

接着,我们发现对于\(dis(2,1),dis(6,1)\)还没有统计进来答案

所以我们需要考虑怎么处理出来这两个距离

我们设\(dis[u]\):表示在以\(u\)为根的子树内的每一个节点到\(u\)的距离的集合

这样就可以将除\(4\)为根的子树外的所有节点所贡献的答案计算出来

也就是\(ans+=dis[1]\)

但是,我们发现一个问题

在这样处理时,\(dis[u]\)会包含以\(4\)为根的子树中的节点到\(1\)的距离

也就是会重复计算

我们设\(dis2[x]\)表示以\(x\)为根的树中,所有节点到\(x\)在点分树中的父亲的距离,也就是到上一个重心的距离

于是我们需要减去\(dis2[4]\),\(dis2[4]\)表示以\(4\)为根的树中,每个节点到\(1\)的距离

也就是\(ans-=dis2[4]\)

这样就是最后的答案,一步步往上推

总结出来就是

\(ans=ans+dis[x]+dis(x,ask)\times(siz[x]-siz[son[x]])-dis2[x]\)

其中,\(siz[son[x]]\)可以在上次处理时用\(lastsiz\)储存,\(dis(x,ask)\)可以用\(lca\)处理,则\(dis[x]\)和\(dis2[x]\)可以在建点分树时处理


好了,上面哔哔的全是假的

题目还有一个区间限制,有了这个区间限制后,该怎么处理呢

我们将做法改良一下:

我们设\(vector:xw[x]\),其中存储以\(x\)为根的子树中的所有节点的信息

我们的 \(dis\) 和 \(dis2\)就可以存储在里面

接着,我们考虑将每个节点的年龄也存进这个\(vector\)里

然后每次对\(vector\)以年龄进行排序,然后对\(dis\)和\(dis2\)进行前缀和,这样\(xw[x][id].dis\)就是储存着,以\(x\)为根的树中,年龄小于等于\(xw[x][id].age\)的节点到\(x\)的距离和

这样,我们在统计答案时,可以输出\(query(ask,r)-query(ask,l-1)\)

对于每个\(query\)中,对于每个\(vector:xw[x]\),进行二分,找出其中年龄小于等于\(queryage\)的节点,设其对应\(vector\)中的位置是\(id\),那么我们的答案就是\(xw[x][id].dis+dis(x,ask)\times(id-lastsiz)-xw[x][id].dis2\)
其中\(id\)也对应着在\(x\)的树中年龄小于等于\(queryage\)的节点的个数

对于\(dis(a,b)\),我们考虑用树链剖分查找\(lca\),得出答案

所以我们就可以快乐的切掉了

详情看代码


代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=150010,INF=0x7fffffff;
int n,q,maxx,cnt=0;
int quan[N];
int a[N];
int to[N<<1],nxt[N<<1],w[N<<1],head[N];
void add(int u,int v,int wi)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    w[cnt]=wi;
    head[u]=cnt;
}
struct edge
{
    int age;
    ll dis,dis2;
}tmp;
vector<edge>xw[N];
bool vis[N];
int maxs[N];
int siz[N];
int father[N];
int rt;
/*动态点分治*/
inline int findrt(int u,int fa,int Size)//求重心
{
    siz[u]=1,maxs[u]=0;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(vis[v]||v==fa)continue;
        findrt(v,u,Size);
        siz[u]+=siz[v];
        maxs[u]=max(maxs[u],siz[v]);
    }
    maxs[u]=max(maxs[u],Size-siz[u]);
    if(maxs[u]<maxs[rt])rt=u;
}
int dist[N];
inline void dfs(int u,int fa,ll pre,int rtt)
{
    xw[rtt].push_back((edge){a[u],pre,dist[u]});
    //因为还没更新,所以dist[u]为到上一个重心的距离,也就是在点分树中到rtt的父亲的距离
    //pre为dis累计
    dist[u]=pre;//更新
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa||vis[v])continue;
        dfs(v,u,pre+w[i],rtt);
    }
}
inline bool cmp(edge p,edge p1)
{
    return p.age<p1.age;
}
inline void solve(int u)
{
    vis[u]=1;
    xw[u].push_back((edge){a[u],0,dist[u]});//将根节点信息存入
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(vis[v])continue;
        dfs(v,u,w[i],u);//处理以u为根的vector
    }
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(vis[v])continue;
        rt=0;
        findrt(v,u,siz[v]);//每次找新的重心
        father[rt]=u;//建点分树
        solve(rt);
    }
    xw[u].push_back((edge){-1,0,0});//加入以防止询问时到达边界
    sort(xw[u].begin(),xw[u].end(),cmp);//排序
    int len=xw[u].size();
    for(int i=1;i<len;i++)xw[u][i].dis+=xw[u][i-1].dis,xw[u][i].dis2+=xw[u][i-1].dis2;//前缀和
}
/* 树链剖分*/
int ind=0;
int d[N];
int sz[N];
int son[N];
int topp[N];
int f[N];
int ddis[N];
void dfs1(int u,int fa)
{
    sz[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)continue;
        d[v]=d[u]+1;
        f[v]=u;
        ddis[v]=ddis[u]+w[i];
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    topp[u]=tp;
    if(son[u])dfs2(son[u],tp);
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==son[u]||v==f[u])continue;
        dfs2(v,v);
    }
}
int lca(int x,int y)
{
    while(topp[x]!=topp[y])
    {
        if(d[topp[x]]<d[topp[y]])swap(x,y);
        x=f[topp[x]];       
    }
    if(d[x]>d[y])return y;
    return x;
}
ll getdis(int x,int y)
{
    int LCA=lca(x,y);
    return 1ll*(ddis[x]+ddis[y]-2ll*ddis[LCA]);
}
/*最后答案*/
inline ll query(int x,int ag)
{
    if(!x)return 0;
    int ask=x;
    ll ans=0ll,pre=0ll;
    int ll,rr,mid,len,id,last_siz=0;
    while(x)
    {
        ll=0,rr=xw[x].size()-1;
        id=rr;
        pre=getdis(x,ask);//即dis(x,ask)
        while(ll<=rr)//二分出年龄小于等于ag的id
        {
            mid=(ll+rr)>>1;
            if(xw[x][mid].age<=ag)id=mid,ll=mid+1;
            else rr=mid-1;
        }
        //加入答案
        if(id>=1)
        {
            ans+=xw[x][id].dis;
            ans+=1ll*(id-last_siz)*pre;
        }
        if(father[x])ans-=xw[x][id].dis2;//如果不是根
        last_siz=id;
        x=father[x];
    }
    return ans;
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main()
{
    n=read(),q=read(),maxx=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int aa,bb,cc;
    for(int i=1;i<n;i++)
    {
        aa=read(),bb=read(),cc=read();
        add(aa,bb,cc),add(bb,aa,cc);
    }
    d[1]=1;
    dfs1(1,0);
    dfs2(1,1);
    rt=0,maxs[rt]=INF;
    findrt(1,0,n);
    solve(rt);
    ll lastans=0ll;
    while(q--)
    {
        aa=read(),bb=read(),cc=read();
        bb=(bb+lastans)%maxx,cc=(cc+lastans)%maxx;
        if(bb>cc)swap(bb,cc);
        printf("%lld\n",lastans=(query(aa,cc)-query(aa,bb-1)));
    }   
    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 
*/
上一篇:[Kattis]redblacktree(树形依赖背包,DP优化)


下一篇:[ZJOI2015]幻想乡战略游戏 - 动态点分治