/category/lca/ zh-CN Fri, 16 Dec 2016 15:59:00 +0800 Fri, 16 Dec 2016 15:59:00 +0800 /archives/149/ /archives/149/ Fri, 16 Dec 2016 15:59:00 +0800 admin ###Description 小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图： ![11(4).png][1] 根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示 ![22(2).png][2] 现在他想问你，树中一些结点对的距离是多少。 ###Input 第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问大树中结点 fr和 to之间的距离是多少。N,M,Q<=100000 ###Output 输出Q行，每行一个整数，第 i行是第 i个询问的答案。 ###Sample Input 5 2 3 1 4 1 3 4 2 4 5 4 3 3 2 6 9 1 8 5 3 ###Sample Output 6 3 3 ###Solution 先对模板树求lca，并按dfs序建一棵主席树 每次向大树上加子树时，先二分查找他的父亲在哪一块，然后在主席树上查接到哪个节点下面 对于每一块，存它的根节点与根节点的父亲在模板树中的编号 然后把每一块视做节点，可以得到一棵大树，对大树也求lca 处理查询时，需要分3种情况：在同一块中，两块在一条链上，两块不在一条链上 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> inline T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define N 100000 namespace zx { struct node { int lc,rc,cnt; }s[2000000]; int sm=1; int modify(int x,int l,int r,int p) { int t=sm++; s[t]=s[x]; s[t].cnt++; if(l^r) { int f=(l+r)>>1; if(p<=f) s[t].lc=modify(s[x].lc,l,f,p); else s[t].rc=modify(s[x].rc,f+1,r,p); } return t; } int kth(int a,int b,int l,int r,int k) { if(l==r)return l; int t=s[s[a].lc].cnt-s[s[b].lc].cnt,f=(l+r)>>1; if(t>=k)return kth(s[a].lc,s[b].lc,l,f,k); return kth(s[a].rc,s[b].rc,f+1,r,k-t); } int root[N+1]; } int n,m,q; namespace t1 { int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1]; struct edge { int to,ne; }e[N<<1]; inline void add(int x,int a,int b) { e[x].to=b,e[x].ne=p[a],p[a]=x; } void dfs(int x) { sz[x]=1; id[x]=++idm; zx::root[id[x]]=zx::modify(zx::root[id[x]-1],1,n,x); for(int i=p[x];i;i=e[i].ne) if(e[i].to^fa[x][0]) fa[e[i].to][0]=x,dep[e[i].to]=dep[x]+1,dfs(e[i].to),sz[x]+=sz[e[i].to]; idr[x]=idm; } inline int dis(int x,int y) { int a=x,b=y,ret=0; if(dep[a]<dep[b]) { for(int i=16;~i;i--) if((dep[b]-dep[a])&(1<<i)) ret+=1<<i,b=fa[b][i]; } else if(dep[a]>dep[b]) { for(int i=16;~i;i--) if((dep[a]-dep[b])&(1<<i)) ret+=1<<i,a=fa[a][i]; } if(a==b)return ret; for(int i=16;~i;i--) if(fa[a][i]^fa[b][i]) a=fa[a][i],b=fa[b][i],ret+=1<<i+1; return ret+2; } } namespace t2 { int cnt=1; ll id[N+1],nid; struct data { int a,b,dep,fa[17],di[17]; }s[N+1]; inline void link(int a,ll b) { int c=std::upper_bound(id,id+cnt,b)-id-1; int cf=s[c].a,d=zx::kth(zx::root[t1::idr[cf]],zx::root[t1::id[cf]-1],1,n,b-id[c]+1); s[cnt].a=a; s[cnt].b=d; s[cnt].dep=s[c].dep+1; s[cnt].fa[0]=c; s[cnt].di[0]=t1::dis(cf,d)+1; id[cnt]=nid; nid+=t1::sz[a]; cnt++; } inline void init() { for(int i=0;i<16;i++) for(int j=0;j<cnt;j++) s[j].fa[i+1]=s[s[j].fa[i]].fa[i],s[j].di[i+1]=s[j].di[i]+s[s[j].fa[i]].di[i]; } inline int lca(int x,int y) { int a=x,b=y; if(s[a].dep<s[b].dep) { for(int i=16;~i;i--) if((s[b].dep-s[a].dep)&(1<<i)) b=s[b].fa[i]; } else if(s[a].dep>s[b].dep) { for(int i=16;~i;i--) if((s[a].dep-s[b].dep)&(1<<i)) a=s[a].fa[i]; } if(a==b)return a; for(int i=16;~i;i--) if(s[a].fa[i]^s[b].fa[i]) a=s[a].fa[i],b=s[b].fa[i]; return s[a].fa[0]; } inline ll linkdis(int p,int q,int x,int y) { ll ret=t1::dis(x,s[p].a)+1; for(int i=16;~i;i--) if((s[p].dep-s[q].dep-1)&(1<<i)) ret+=s[p].di[i],p=s[p].fa[i]; return ret+t1::dis(s[p].b,y); } inline ll dis(ll x,ll y) { int p=std::upper_bound(id,id+cnt,x)-id-1,q=std::upper_bound(id,id+cnt,y)-id-1; int xid=zx::kth(zx::root[t1::idr[s[p].a]],zx::root[t1::id[s[p].a]-1],1,n,x-id[p]+1); int yid=zx::kth(zx::root[t1::idr[s[q].a]],zx::root[t1::id[s[q].a]-1],1,n,y-id[q]+1); if(p==q)return t1::dis(xid,yid); int t=lca(p,q); if(t==p)return linkdis(q,p,yid,xid); if(t==q)return linkdis(p,q,xid,yid); ll ret=t1::dis(xid,s[p].a)+t1::dis(yid,s[q].a)+2; for(int i=16;~i;i--) if((s[p].dep-s[t].dep-1)&(1<<i)) ret+=s[p].di[i],p=s[p].fa[i]; for(int i=16;~i;i--) if((s[q].dep-s[t].dep-1)&(1<<i)) ret+=s[q].di[i],q=s[q].fa[i]; return ret+t1::dis(s[p].b,s[q].b); } } int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); t1::add(i<<1,a,b); t1::add(i<<1|1,b,a); } zx::root[0]=zx::sm++; t1::fa[1][0]=1; t1::dfs(1); for(int i=0;i<16;i++) for(int j=1;j<=n;j++) t1::fa[j][i+1]=t1::fa[t1::fa[j][i]][i]; t2::s[0].a=1; t2::id[0]=1; t2::nid=n+1; while(m--) { int a; ll b; scanf("%d%lld",&a,&b); t2::link(a,b); } t2::init(); while(q--) { ll a,b; scanf("%lld%lld",&a,&b); printf("%lld\n",t2::dis(a,b)); } } ``` [1]: /usr/uploads/2016/12/1348856476.png [2]: /usr/uploads/2016/12/2791822739.png ]]> 0 /archives/149/#comments /feed/archives/149/