BZOJ4381[POI2015]Odwiedziny——分块+长链剖分-白红宇

BZOJ4381[POI2015]Odwiedziny——分块+长链剖分

阅读量：6291 次

发布时间：2019-06-22

本文共 3250 字，大约阅读时间需要 10 分钟。

题目描述

给定一棵n个点的树，树上每条边的长度都为1，第i个点的权值为a[i]。

Byteasar想要走遍这整棵树，他会按照某个1到n的全排列b走n-1次，第i次他会从b[i]点走到b[i+1]点，并且这一次的步伐大小为c[i]。

对于一次行走，假设起点为x，终点为y，步伐为k，那么Byteasar会从x开始，每步往前走k步，如果最后不足k步就能到达y，那么他会一步走到y。

请帮助Byteasar统计出每一次行走时经过的所有点的权值和。

输入

第一行包含一个正整数n(2<=n<=50000)。表示节点的个数。

第二行包含n个正整数，其中第i个数为a[i](1<=a[i]<=10000)，分别表示每个点的权值。

接下来n-1行，每行包含两个正整数u,v(1<=u,v<=n)，表示u与v之间有一条边。

接下来一行包含n个互不相同的正整数，其中第i个数为b[i](1<=b[i]<=n)，表示行走路线。

接下来一行包含n-1个正整数，其中第i个数为c[i](1<=c[i]<n)，表示每次行走的步伐大小。

输出

包含n-1行，每行一个正整数，依次输出每次行走时经过的所有点的权值和

样例输入

1 2 3 4 5

1 2

2 3

3 4

3 5

4 1 5 2 3

1 3 1 1

样例输出

　　因为k的大小不确定，所以分情况来做。设p=sqrt(n)，当k<=p时，可以预处理出f[i][j]表示i节点以j步伐一直往上走，直到走到根节点(i节点的深度如果不是k的倍数，根节点不计入)为止能得到的点权和，查询时直接求就好了.当k>p时,就要暴力往上走了,可以用重链剖分来实现,单次查询时间复杂度是O(logn+√n)，但有一种时间复杂度更优的做法——长链剖分，因为长链剖分可以O(1)查询一个点的k级祖先，因此最多爬√n次，单次查询时间复杂度O(√n)。如何实现参见->。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define ll long longusing namespace std;int n;int x,y;int tot;int mask;int b[50010];int a[50010];int k[50010];int d[50010];int st[50010];int mx[50010];int to[100010];int son[50010];int top[50010];int head[50010];int next[100010];int f[50010][17];int up[50010][300];vector
                
                 s[50010];vector
                 
                  t[50010];void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y;}void dfs(int x){ d[x]=d[f[x][0]]+1; mx[x]=d[x]; for(int i=1;i<=16;i++) { if(f[x][i-1]) { f[x][i]=f[f[x][i-1]][i-1]; } else { break; } } int fx=x; for(int i=1;i<=mask;i++) { fx=f[fx][0]; up[x][i]=a[x]+up[fx][i]; } for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x][0]) { f[to[i]][0]=x; dfs(to[i]); mx[x]=max(mx[x],mx[to[i]]); if(mx[to[i]]>mx[son[x]]) { son[x]=to[i]; } } }}void dfs2(int x,int tp){ top[x]=tp; if(son[x]) { dfs2(son[x],tp); } for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x][0]&&to[i]!=son[x]) { dfs2(to[i],to[i]); } }}void find(int x){ int rt=x; int len=mx[x]-d[x]; x=f[rt][0]; while(d[rt]-d[x]<=len&&x) { s[rt].push_back(x); x=f[x][0]; } x=rt; while(son[x]) { t[rt].push_back(son[x]); x=son[x]; }}int find_ancestor(int x,int k){ if(k==0) { return x; } if(d[x]<=k) { return 0; } x=f[x][st[k]]; k-=(1<
                  
                   =0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0];}int query(int x,int y,int step){ int res=0; int anc=lca(x,y); int lx=d[x]-d[anc]; int ly=d[y]-d[anc]; if(step>mask) { res+=a[x]+a[y]; while(lx>step) { x=find_ancestor(x,step); res+=a[x]; lx-=step; } if(lx+ly-1>=step) { y=find_ancestor(y,lx+ly-(lx+ly-1)/step*step); res+=a[y]; ly=(lx+ly-1)/step*step-lx; while(ly>step) { y=find_ancestor(y,step); res+=a[y]; ly-=step; } } if(x!=anc&&y!=anc&&(lx==step||ly==step)) { res+=a[anc]; } } else { if(lx+ly<=step) { res=a[x]+a[y]; } else { res+=a[y]; y=find_ancestor(y,lx+ly-(lx+ly-1)/step*step); ly=(lx+ly-1)/step*step-lx; res+=up[x][step]-up[find_ancestor(x,(lx/step)*step+step)][step]; if(ly>=0) { res+=up[y][step]-up[find_ancestor(y,(ly/step)*step+step)][step]; } if(lx%step==0) { res-=a[anc]; } } } return res;}int main(){ scanf("%d",&n); mask=sqrt(n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i
                   
                    >1]+1; } for(int i=1;i<=n;i++) { scanf("%d",&b[i]); } for(int i=1;i

转载于:https://www.cnblogs.com/Khada-Jhin/p/9581321.html

你可能感兴趣的文章