---
title: Codeforce 342 E. Xenia and Tree 解析(思維、重心剖分)
description: "Codeforce 342 E. Xenia and Tree 解析(思維、重心剖分)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 342 E. Xenia and Tree 解析(思維、重心剖分)">
<!-- toc -->

# Codeforce 342 E. Xenia and Tree 解析(思維、重心剖分)
今天我們來看看CF342E
[題目連結](https://codeforces.com/problemset/problem/342/E)

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

### 前言
這題我是當作學習重心剖分的習題看待的，最詳細的版本請看[教學文](https://zhanghuimeng.github.io/post/centroid-decomposition-summaary-and-example/)

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
每兩個樹上的點，其重心剖分樹(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](https://codeforces.com/contest/342/submission/91884169)