小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個結點的大小順序是一致的。下面給出一個實例。假設模板樹如下圖:
根據第(1)步,初始的大樹與模板樹是相同的。在(2.1)步,假設選擇了a=4,b=3。運行(2.2)和(2.3)后,得到新的大樹如下圖所示
現在他想問你,樹中一些結點對的距離是多少。
第一行三個整數: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
輸出Q行,每行一個整數,第 i行是第 i個詢問的答案。
經過兩次操作后,大樹變成了下圖所示的形狀:結點6到9之間經過了6條邊,所以距離為6;類似地,結點1到8之間經過了3條邊;結點5到3之間也經過了3條邊。
正解:dfs序主席樹+lca
惡心數據結構題+碼農題。。前后總共調了6個多小時。。WA顯示成RE也無語至極。。
具體做法:
首先對于模板樹進行預處理,dfs一遍得到dfs序,為了維護子樹第k小編號的查詢操作,構主席樹。
(ps:在主席樹上查找子樹第
對于復制操作,復制操作的話對于每次復制我只需要記錄這次復制的這棵子樹的根,根接到了哪個點的下方,當然上述記錄的都是在原樹中的相應編號。同時為了方便之后計算這棵子樹內到根的距離,不妨記錄一下根在原樹到
對于最后的查詢操作,需要仔細考慮了,有很多細節。當
//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define N (100010)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;il ll gll(){ ll x=0,q=1; char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}struct edge{ ll nt,to,dis; };struct tree{ ll head[N],dfn[N],tid[N],dis[N],id[N],anc[N],up[N],size[N],top[N],fa[N],son[N],dep[N],n,num,cnt,tot; edge g[2*N]; il void insert(ll from,ll to,ll dis){ g[++num]=(edge){head[from],to,dis},head[from]=num; return; } il void dfs1(ll x,ll p){ dep[x]=dep[p]+1,fa[x]=p,size[x]=1; ll mx=0,v; for (RG ll i=head[x];i;i=g[i].nt){ v=g[i].to; if (v==p) continue; dis[v]=dis[x]+g[i].dis; dfs1(v,x); size[x]+=size[v]; if (size[mx]<=size[v]) mx=v; } son[x]=mx; return; } il void dfs2(ll x,ll p,ll a){ dfn[++cnt]=x,tid[x]=cnt,top[x]=a; if (son[x]) dfs2(son[x],x,a); ll v; for (RG ll i=head[x];i;i=g[i].nt){ v=g[i].to; if (v==p || v==son[x]) continue; dfs2(v,x,v); } return; } il ll lca(ll u,ll v){ while (top[u]!=top[v]){ if (dep[top[u]]<dep[top[v]]) swap(u,v); u=fa[top[u]]; } return dep[u]>dep[v] ? v : u; } il ll jump(ll u,ll v){ ll x=u; while (top[u]!=top[v]) x=top[u],u=fa[top[u]]; return u==v ? x : son[v]; } }tr1,tr2;struct chairtree{ ll root[N],sum[20*N],ls[20*N],rs[20*N],sz; il void build(ll x,ll &y,ll l,ll r,ll v){ sum[y=++sz]=sum[x]+1,ls[y]=ls[x],rs[y]=rs[x]; if (l==r) return; ll mid=(l+r)>>1; if (v<=mid) build(ls[x],ls[y],l,mid,v); else build(rs[x],rs[y],mid+1,r,v); return; } il ll query(ll x,ll y,ll l,ll r,ll k){ if (l==r) return l; ll mid=(l+r)>>1; if (k<=sum[ls[y]]-sum[ls[x]]) return query(ls[x],ls[y],l,mid,k); else return query(rs[x],rs[y],mid+1,r,k-sum[ls[y]]+sum[ls[x]]); } }ch;il ll find(ll x){ if (x<=tr1.n) return 1; ll l=1,r=tr2.n,mid,ans=1; while (l<=r){ mid=(l+r)>>1; if (x<tr2.id[mid]) r=mid-1; else ans=mid,l=mid+1; } return ans;}il ll query(ll blv,ll v){ if (v<=tr1.n) return v; v-=tr2.id[blv]-1; ll x=tr2.anc[blv],l=tr1.tid[x],r=l+tr1.size[x]-1; return ch.query(ch.root[l-1],ch.root[r],1,tr1.n,v);}il void work(){ tr1.n=gll(); ll m=gll(),q=gll(); for (RG ll i=1;i<tr1.n;++i){ ll u=gll(),v=gll(); tr1.insert(u,v,1),tr1.insert(v,u,1); } tr1.dfs1(1,0),tr1.dfs2(1,0,1); tr2.id[1]=1,tr2.anc[1]=1,tr2.n=1,tr2.tot=tr1.n; for (RG ll i=1;i<=tr1.n;++i) ch.build(ch.root[i-1],ch.root[i],1,tr1.n,tr1.dfn[i]); for (RG ll i=1;i<=m;++i){ ll u=gll(),v=gll(),blv=find(v),idv=query(blv,v); tr2.n++,tr2.id[tr2.n]=tr2.tot+1,tr2.tot+=tr1.size[u],tr2.anc[tr2.n]=u,tr2.up[tr2.n]=idv; tr2.insert(blv,tr2.n,tr1.dis[idv]-tr1.dis[tr2.anc[blv]]+1); } tr2.dfs1(1,0),tr2.dfs2(1,0,1); for (RG ll i=1;i<=q;++i){ ll u=gll(),v=gll(),blu=find(u),blv=find(v); ll idu=query(blu,u),idv=query(blv,v),lca,ans=0; if (blu==blv){ lca=tr1.lca(idu,idv); ans=tr1.dis[idu]+tr1.dis[idv]-2*tr1.dis[lca]; PRintf("%lld/n",ans); continue; } if (tr2.dep[blu]>tr2.dep[blv]) swap(u,v),swap(blu,blv),swap(idu,idv); lca=tr2.lca(blu,blv); if (blu!=lca){ ans=tr1.dis[idu]-tr1.dis[tr2.anc[blu]]; u=tr2.jump(blu,lca); ans+=tr2.dis[blu]-tr2.dis[u]+1; u=tr2.up[u]; }else u=query(blu,u); ans+=tr1.dis[idv]-tr1.dis[tr2.anc[blv]]; v=tr2.jump(blv,lca); ans+=tr2.dis[blv]-tr2.dis[v]+1; v=tr2.up[v],lca=tr1.lca(u,v); ans+=tr1.dis[u]+tr1.dis[v]-2*tr1.dis[lca]; printf("%lld/n",ans); } return;}int main(){ File("tree"); work(); return 0;}//鬼畜dfs序+主席樹+lca沃日
新聞熱點
疑難解答