[BZOJ4539][Hnoi2016]树（倍增+LCA+主席树）

2019-11-08 18:28:52

字体：大中小

来源：转载

供稿：网友

=== ===

这里放传送门

=== ===

题解

这题某天学长出过胡策。。第一眼拿到题，woc，这不就是个裸倍增？第二眼，woc，节点数最大到1e10，这是要死的节奏。。。

这题写起来真 · 麻烦死人。。基本思路是每次把复制的模板树的那个子树缩成一个点，初始的那一整个模板树也缩成一个点，那么大树上最多只会有m+1个点。然后每次查询的时候就可以先定位在模板树上的节点，再在大树上跑倍增，最后再定位到模板树上的具体节点，然后时间复杂度就是科学的O(nlogn)了。。

具体来说，首先缩点以后大树的边上就出现了边权，相邻两个节点之间的边权设定为当把大树展开时这两个节点所代表子树的根节点之间的距离。为了知道这一个我们还要知道当大树上一个节点下面挂了另一个节点的时候它实际上是从哪一个具体的节点接入的，这样才能计算它进入这个节点代表的子树以后再跑多久才能到达这棵子树的根节点。这个在处理修改操作的时候记录下来就可以。这样处理出了一棵带边权的大树，然后对大树进行dfs处理出倍增所需要的数组。

而在这里还有一个问题就是如何定位到模板树中的具体节点，因为每次接入子树以后节点会被按照原来的大小顺序重新编号，而当我们想定位某个节点的时候我们知道它现在的编号，那么就可以通过在修改操作中进行二分来知道它是哪一个操作接进去的，然后就可以知道它具体在模板树的哪棵子树里，然后还可以通过它现在的编号知道它是这棵子树里编号第几大的点。要知道具体是哪个点就要查询子树中第k大了，那么就要对dfs序建立主席树来搞这个东西。

每次查询的时候首先定位当前所在模板树子树的节点，然后计算出它到根节点的距离，因为这部分相当于是大树上的“半个节点”，不能直接跑倍增。接下来用倍增算出“整个节点”的部分。但是这样会有一些多算了，因为直接跑倍增的时候是相当于跑到那个子树的根节点的，但实际上可能还没到根节点就走到LCA了。所以我们需要找到路径两边的节点x和y分别是在哪个节点接入的，然后就可以算出它实际上的LCA，多算的那一部分就是实际LCA和子树根节点距离的两倍，减掉就可以了。

代码

#include<cstdio>#include<cstring>#include<algorithm>#define Pow 17using namespace std;int n,m,q,p[100010],a[200010],next[200010],tot,deep[100010],size[100010],f[100010][20];int w[100010],root[100010],cnt,out[100010],in[100010],cur[100010];long long sum;struct Operate{ int a; long long b,l,r;}k[100010];struct segtree{ int l,r,val;}t[4000010];void add(int x,int y){tot++;a[tot]=y;next[tot]=p[x];p[x]=tot;}/*void dfs(int u){ deep[u]=deep[f[u][0]]+1; for (int i=1;i<=Pow;i++) f[u][i]=f[f[u][i-1]][i-1]; size[u]=1;w[++w[0]]=u;in[u]=w[0]; for (int i=p[u];i!=0;i=next[i]) if (a[i]!=f[u][0]){ f[a[i]][0]=u; dfs(a[i]); size[u]+=size[a[i]]; } out[u]=w[0];}*/void dfs(){ int u=1; bool flag; while (true){ if (deep[u]==0){ deep[u]=deep[f[u][0]]+1; for (int i=1;i<=Pow;i++) f[u][i]=f[f[u][i-1]][i-1]; size[u]=1;w[++w[0]]=u; in[u]=w[0];cur[u]=p[u]; } flag=false; for (int i=cur[u];i!=0;i=next[i]){ cur[u]=next[i]; if (a[i]!=f[u][0]){ f[a[i]][0]=u; u=a[i];flag=true;break; } } if (flag==false){ out[u]=w[0]; if (u==1) break; else{ int v=f[u][0]; size[v]+=size[u];u=v; } } }}void insert(int &i,int j,int l,int r,int v){ i=++cnt;t[i]=t[j]; t[i].val++; if (l==r) return; int mid=(l+r)>>1; if (v<=mid) insert(t[i].l,t[j].l,l,mid,v); else insert(t[i].r,t[j].r,mid+1,r,v);}int Find_rank(int i,int j,int l,int r,int k){ if (l==r) return l; int tmp=t[t[j].l].val-t[t[i].l].val,mid=(l+r)>>1; if (tmp>=k) return Find_rank(t[i].l,t[j].l,l,mid,k); else return Find_rank(t[i].r,t[j].r,mid+1,r,k-tmp);}int find(long long x){ int l,r,mid; l=1;r=m+1; while (l<=r){ int mid=(l+r)>>1; if (k[mid].l>x) r=mid-1; else if (k[mid].r<x) l=mid+1; else return mid; } return 0;}int Findpoint(int i,long long x){ long long rt,rk; rt=k[i].a;rk=x-k[i].l+1; return Find_rank(root[in[rt]-1],root[out[rt]],1,n,rk);}namespace Bigtree{ int p[100010],a[200010],next[200010],w[200010],tot,deep[100010],f[100010][20]; int cur[100010],g[100010][20],last[100010][20]; void add(int x,int y,int v){ tot++;a[tot]=y;next[tot]=p[x];w[tot]=v;p[x]=tot; }/* void dfs(int u){ deep[u]=deep[f[u][0]]+1; for (int i=1;i<=Pow;i++){ f[u][i]=f[f[u][i-1]][i-1]; g[u][i]=g[u][i-1]+g[f[u][i-1]][i-1]; last[u][i]=last[f[u][i-1]][i-1]; } for (int i=p[u];i!=0;i=next[i]) if (a[i]!=f[u][0]){ f[a[i]][0]=u; g[a[i]][0]=w[i]; last[a[i]][0]=a[i]; dfs(a[i]); } }*/ void dfs(){ int u=1; bool flag; while (true){ if (deep[u]==0){ deep[u]=deep[f[u][0]]+1;cur[u]=p[u]; for (int i=1;i<=Pow;i++){ f[u][i]=f[f[u][i-1]][i-1]; g[u][i]=g[u][i-1]+g[f[u][i-1]][i-1]; last[u][i]=last[f[u][i-1]][i-1]; } } flag=false; for (int i=cur[u];i!=0;i=next[i]){ cur[u]=next[i]; if (a[i]!=f[u][0]){ f[a[i]][0]=u; g[a[i]][0]=w[i]; last[a[i]][0]=a[i]; u=a[i];flag=true;break; } } if (flag==false) if (u==1) break; else u=f[u][0]; } } long long FindLCA(int &lca,long long &f1,long long &f2,int x,int y){ long long ans=0; bool s=false; f1=x;f2=y; if (deep[x]!=deep[y]){ if (deep[x]<deep[y]){ swap(x,y);swap(f1,f2);s=true; } for (int i=Pow;i>=0;i--) if (deep[f[x][i]]>=deep[y]){ f1=last[x][i];ans+=g[x][i];x=f[x][i]; } } for (int i=Pow;i>=0;i--) if (f[x][i]!=f[y][i]){ ans+=g[x][i]+g[y][i]; f1=last[x][i];f2=last[y][i]; x=f[x][i];y=f[y][i]; } while (x!=y){ ans+=g[x][0]+g[y][0]; f1=last[x][0];f2=last[y][0]; x=f[x][0];y=f[y][0]; } if (s==true) swap(f1,f2); lca=x;return ans; }}long long Calcdis(int i,long long x){ int pt=Findpoint(i,x); return deep[pt]-deep[k[i].a];}void Link(int i,int x,long long y){ int u=find(y),dis; dis=Calcdis(u,y); Bigtree::add(i,u,dis+1); Bigtree::add(u,i,dis+1);}long long findlca(long long r1,long long r2,int p){//求出r1，r2两个在区间k[p]里面的节点的lca并返回 int x,y; x=Findpoint(p,r1); y=Findpoint(p,r2); if (deep[x]!=deep[y]){ if (deep[x]<deep[y]) swap(x,y); for (int i=Pow;i>=0;i--) if (deep[f[x][i]]>=deep[y]) x=f[x][i]; } for (int i=Pow;i>=0;i--) if (f[x][i]!=f[y][i]){ x=f[x][i];y=f[y][i]; } while (x!=y){ x=f[x][0];y=f[y][0]; } return deep[x]-deep[k[p].a];}int main(){ scanf("%d%d%d",&n,&m,&q); for (int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs();sum=n; for (int i=1;i<=n;i++) insert(root[i],root[i-1],1,n,w[i]); k[1].l=1;k[1].r=n;k[1].a=1; for (int i=2;i<=m+1;i++){ scanf("%d%lld",&k[i].a,&k[i].b);//注意用long long k[i].l=sum+1;k[i].r=sum+size[k[i].a]; sum+=size[k[i].a]; } for (int i=2;i<=m+1;i++) Link(i,k[i].a,k[i].b); Bigtree::dfs(); for (int i=1;i<=q;i++){ long long x,y,f1,f2,ans=0; int r1,r2,lca; scanf("%lld%lld",&x,&y); r1=find(x);r2=find(y); ans+=Calcdis(r1,x); ans+=Calcdis(r2,y);//计算出两个端点在它们小区间里到根节点的距离 ans+=Bigtree::FindLCA(lca,f1,f2,r1,r2);//计算出两个端点在大树里整块的距离 if (r1==lca) f1=x;else f1=k[f1].b; if (r2==lca) f2=y;else f2=k[f2].b; ans-=2*findlca(f1,f2,lca); //减去进入lca的模板树区间的两个点的lca到模板树区间根节点的距离 PRintf("%lld/n",ans); } return 0;}