BZOJ4539: [Hnoi2016]樹

Description

　　小A想做一棵很大的樹，但是他手上的材料有限，只好用點小技巧了。

　　開始，小A只有一棵結點數(shù)為N的樹，結點的編號為1,2,…,N，其中結點1為根；我們稱這顆樹為模板樹。

　　小A決定通過這棵模板樹來構建一顆大樹。

　　構建過程如下：

　　（1）將模板樹復制為初始的大樹。

　　（2）以下(2.1)(2.2)(2.3)步循環(huán)執(zhí)行M次

　　　　（2.1）選擇兩個數(shù)字a,b，其中1<=a<=N，1<=b<=當前大樹的結點數(shù)。

　　　　（2.2）將模板樹中以結點a為根的子樹復制一遍，掛到大樹中結點b的下方(也就是說，模板樹中的結點a為根的子樹復制到大樹中后，將成為大樹中結點b的子樹)。

　　　　（2.3）將新加入大樹的結點按照在模板樹中編號的順序重新編號。

　　例如，假設在進行2.2步之前大樹有L個結點，模板樹中以a為根的子樹共有C個結點，那么新加入模板樹的C個結點在大樹中的編號將是L+1,L+2,…,L+C；

　　大樹中這C個結點編號的大小順序和模板樹中對應的C個結點的大小順序是一致的。

　　下面給出一個實例。假設模板樹如下圖：

　　根據(jù)第(1)步，初始的大樹與模板樹是相同的。

　　在(2.1)步，假設選擇了a=4，b=3。運行(2.2)和(2.3)后，得到新的大樹如下圖所示

　　現(xiàn)在他想問你，樹中一些結點對的距離是多少。

Input

第一行三個整數(shù)：N,M,Q，以空格隔開，N表示模板樹結點數(shù)，M表示第(2)中的循環(huán)操作的次數(shù)，Q 表示詢問數(shù)量。

接下來N-1行，每行兩個整數(shù) fr,to，表示模板樹中的一條樹邊。

再接下來M行，每行兩個整數(shù)x,to，表示將模板樹中 x 為根的子樹復制到大樹中成為結點to的子樹的一次操作。

再接下來Q行，每行兩個整數(shù)fr,to，表示詢問大樹中結點 fr和 to之間的距離是多少。

N,M,Q<=100000

Output

輸出Q行，每行一個整數(shù)，第 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

HINT

經(jīng)過兩次操作后，大樹變成了下圖所示的形狀：



結點6到9之間經(jīng)過了6條邊，所以距離為6；類似地，結點1到8之間經(jīng)過了3條邊；結點5到3之間也經(jīng)過了3條邊。

題解Here!

真心不想復制了，請您戳這里。

順手貼上代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #define MAXN 100010 using namespace std; int n,m,q,c=1; int id[MAXN],pos[MAXN],tree_size[MAXN]; inline long long read(){long long date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } namespace ST{int d=1,e=1;int head[MAXN],deep[MAXN],f[MAXN][20];struct Tree{int next,to;}a[MAXN<<1];inline void add(int x,int y){a[d].to=y;a[d].next=head[x];head[x]=d++;a[d].to=x;a[d].next=head[y];head[y]=d++;}void buildtree(int rt){tree_size[rt]=1;id[rt]=e;pos[e++]=rt;for(int i=head[rt];i;i=a[i].next){int will=a[i].to;if(!deep[will]){deep[will]=deep[rt]+1;f[will][0]=rt;buildtree(will);tree_size[rt]+=tree_size[will];}}}void step(){for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];}int LCA(int x,int y){if(deep[x]<deep[y])swap(x,y);for(int i=19;i>=0;i--)if(deep[f[x][i]]>=deep[y])x=f[x][i];if(x==y)return x;for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}return f[x][0];}inline long long dis(int x,int y){return abs(deep[x]-deep[y]);}inline long long dis_lca(int x,int y,int rt){return deep[LCA(x,y)]-deep[rt];} } namespace CT{int d=1,size=1,root[MAXN];struct Charman_Tree{int l,r,sum;}a[MAXN*22];struct Right{int root,x;long long v;friend bool operator <(const Right p,const Right q){return p.v<q.v;}}right[MAXN];void insert(int k,int l,int r,int &rt){a[size]=a[rt];rt=size++;a[rt].sum++;if(l==r)return;int mid=l+r>>1;if(k<=mid)insert(k,l,mid,a[rt].l);else insert(k,mid+1,r,a[rt].r);}int query(int i,int j,int l,int r,int k){if(l==r)return l;int mid=l+r>>1,t=a[a[j].l].sum-a[a[i].l].sum;if(k<=t)return query(a[i].l,a[j].l,l,mid,k);else return query(a[i].r,a[j].r,mid+1,r,k-t);}inline void buildtree(){root[0]=0;a[0].l=a[0].r=a[0].sum=0;for(int i=1;i<=n;i++){root[i]=root[i-1];insert(pos[i],0,n,root[i]);}}inline int kth(int l,int r,int k){return query(root[l],root[r],0,n,k);}inline void insert_node(int root,int x){right[d]=(Right){root,x,right[d-1].v+tree_size[root]};d++;}inline void query_node(long long v,int &root,int &y,int &x){Right p=*lower_bound(right+1,right+d,(Right){0,0,v});root=p.root;x=p.x;int rank=v+tree_size[root]-p.v;y=kth(id[root]-1,id[root]+tree_size[root]-1,rank);} } namespace BT{int d=1,head[MAXN],deep[MAXN],val[MAXN],f[MAXN][20];long long dis[MAXN];struct Tree{int next,to;long long w;}a[MAXN<<1];inline void add(int u,int v,long long w){a[d].to=v;a[d].w=w;a[d].next=head[u];head[u]=d++;a[d].to=u;a[d].w=w;a[d].next=head[v];head[v]=d++;}void buildtree(int rt){int will;for(int i=head[rt];i;i=a[i].next){will=a[i].to;if(!deep[will]){deep[will]=deep[rt]+1;dis[will]=dis[rt]+a[i].w;f[will][0]=rt;buildtree(will);}}}void step(){for(int i=1;i<=19;i++)for(int j=1;j<=c-1;j++)f[j][i]=f[f[j][i-1]][i-1];}int LCA(int x,int y,int &u,int &v){if(x==y)return x;if(deep[x]<deep[y]){swap(x,y);swap(u,v);}for(int i=19;i>=0;i--)if(deep[f[x][i]]>deep[y])x=f[x][i];if(f[x][0]==y){u=val[x];return y;}else if(deep[x]!=deep[y])x=f[x][0];for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}u=val[x];v=val[y];return f[x][0];}inline long long dist(int u,int v,int lca){return dis[u]+dis[v]-dis[lca]*2;} } inline void solve(long long x,long long y){long long dist;int r1,x1,y1,h1;int r2,x2,y2,h2;CT::query_node(x,r1,y1,x1);CT::query_node(y,r2,y2,x2);h1=y1;h2=y2;int lca=BT::LCA(x1,x2,h1,h2),r=CT::right[lca].root;dist=ST::dis(r1,y1)+ST::dis(r2,y2)-ST::dis_lca(h1,h2,r)*2+BT::dist(x1,x2,lca);printf("%lld\n",dist); } void work(){long long x,y;while(q--){x=read();y=read();solve(x,y);} } void init(){int x,y,rt;n=read();m=read();q=read();for(int i=1;i<n;i++){x=read();y=read();ST::add(x,y);}ST::deep[1]=1;ST::buildtree(1);ST::step();CT::buildtree();CT::insert_node(1,c++);for(int i=1;i<=m;i++){int u=read();long long v=read();CT::query_node(v,rt,y,x);CT::insert_node(u,c);BT::val[c]=y;int w=ST::dis(y,rt)+1;BT::add(x,c,w);c++;}BT::deep[1]=1;BT::dis[1]=0;BT::buildtree(1);BT::step(); } int main(){init();work();return 0; }

?

轉載于:https://www.cnblogs.com/Yangrui-Blog/p/9343782.html

總結

以上是生活随笔為你收集整理的BZOJ4539: [Hnoi2016]树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。