Codeforce 342 E. Xenia and Tree 解析(思維、重心剖分)

今天我們來看看CF342E

題目連結

題目

給你一棵樹，有兩種操作，把某點標成紅色或者查詢離某點最近的紅點有多遠。

前言

這題我是當作學習重心剖分的習題看待的，最詳細的版本請看教學文

想法

每兩個樹上的點，其重心剖分樹(CD樹)上的\(LCA\)一定在其最短路徑上。因此當我們把點\(v\)塗成紅色時，我們只需要更改CD樹上\(v\)的祖先到最近的紅點的距離就好。

令\(ans[v]\)代表\(v\)子樹(CD樹上的子樹)上到離\(v\)最近的紅點的距離。假設把\(v\)塗色，\(j\)為\(v\)在CD樹上的某個祖先，\(ans[j]=min(ans[j],dist(v,j))\)，\(dist(v,j)\)代表在原圖上\(v,j\)間的最短距離，我們可以用老方法:\(dist(v,j)=dep[v]+dep[j]-2\times dep[lca(v,j)]\)，\(dep[v]\)是\(v\)在原圖的深度。

而要搜尋離\(v\)最近的紅點距離時，由於兩點間的最短距離上一定有CD樹上\(v\)的祖先，因此我們遍歷那些祖先(點\(j\))，找\(dist(v,j)+ans[j]\)的最小值。

程式碼:

const int _n=1e5+10;

int t,n,m,aa,bb,vv,ans[_n];

VI G[_n];

int sz[_n],cd_fa[_n];

bool del[_n];

void dfsSz(int v,int faa){

  sz[v]=1;

  rep(i,0,SZ(G[v]))if(G[v][i]!=faa and !del[G[v][i]])dfsSz(G[v][i],v),sz[v]+=sz[G[v][i]];

}

int get_centroid(int v,int faa,int cnt){

  rep(i,0,SZ(G[v]))if(G[v][i]!=faa and !del[G[v][i]] and sz[G[v][i]]>cnt/2)

    return get_centroid(G[v][i],v,cnt);

  return v;

}

void centroid_decomposition(int v,int faa){

  dfsSz(v,faa);int centroid=get_centroid(v,faa,sz[v]);

  cd_fa[centroid]=faa,del[centroid]=1;

  rep(i,0,SZ(G[centroid]))if(G[centroid][i]!=faa and !del[G[centroid][i]])

    centroid_decomposition(G[centroid][i],centroid);

}

const int MAXB=18;

int dep[_n],fa[_n][MAXB];

void dfs(int v,int faa,int d){

  dep[v]=d;fa[v][0]=faa;

  rep(i,0,SZ(G[v]))if(faa!=G[v][i])dfs(G[v][i],v,d+1);

}

void bfa(){

  rep(j,1,MAXB)rep(i,1,n+1)if(~fa[i][j-1])

    fa[i][j]=fa[fa[i][j-1]][j-1];

}

int lca(int a,int b){

  if(dep[a]<dep[b])swap(a,b);

  per(j,0,MAXB)if(~fa[a][j] and dep[fa[a][j]]>=dep[b])a=fa[a][j];

  if(a==b)return a;

  per(j,0,MAXB)if(~fa[a][j] and fa[a][j]!=fa[b][j])a=fa[a][j],b=fa[b][j];

  return fa[a][0];

}

void update(int vv){

  int b=vv;

  while(b!=-1){

    int l=lca(vv,b);

    ans[b]=min(ans[b],dep[vv]+dep[b]-2*dep[l]);

    b=cd_fa[b];

  }

}

main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  cin>>n>>m;rep(i,0,n-1){cin>>aa>>bb;G[aa].pb(bb),G[bb].pb(aa);}

  dfs(1,-1,0);rep(i,1,n+1)rep(j,1,MAXB)fa[i][j]=-1; bfa();

  centroid_decomposition(1,-1);rep(i,1,n+1)ans[i]=1e5;

  update(1);

  while(m--){

    cin>>t>>vv;

    if(t==1)update(vv);

    else{

      int minn=1e9,b=vv;

      while(b!=-1){

        int l=lca(vv,b);

        minn=min(minn,ans[b]+dep[b]+dep[vv]-2*dep[l]);

        b=cd_fa[b];

      }cout<<minn<<'\n';

    }

  }

  return 0;

}

標頭、模板請點Submission看

Submission