ABC014 D - 閉路
2019/11/11
$ N頂点の木が与えられます。閉路を持たない木に対して、辺を追加すると、ちょうど一つの閉路を持ちます。
辺が一本ずつ$ Q本与えられるので、それぞれに対して閉路の長さを出力してください。
制約
$ 1\leq N \leq 10^5
$ 1\leq Q \leq 10^5
ポイント
lowest common ancestor(LCA, 最小共通祖先)を考えると、閉路を扱いやすくなる
LCAを高速に求める方法として、ダブリングがある。
https://gyazo.com/60f5d6ca3c431d851cf07b6f7bad5fed
解説記事
自分なりの解説
類題
?
code:c++
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) #define all(a) (a).begin(),(a).end() typedef long long ll;
const int MAX_V = 100000;
const int MAX_LOG_V = 17;
using Graph = vector<vector<int>>;
Graph G(MAX_V);
//2^0個上の親を計算する(DFS)
void dfs(int v,int p, int d){
if(nv == p)continue;
dfs(nv, v, d+1);
}
}
//初期化(ダブリング(前処理))
void init(int V){
dfs(0,-1,0);
for(int k = 0; k + 1 < MAX_LOG_V; ++k){
for(int v = 0; v < V; ++v){
if(parentkv<0)parentk+1v = -1; else{
}
}
}
}
int lca(int u, int v){
//depthu<depthvを担保(vの方が深い) if(depthu>depthv)swap(u, v); //uとvの深さが同じになるまで、bを登らせる(depthu = depthvとなる) for(int k = 0; k < MAX_LOG_V; ++k){
if((depthv-depthu) >> k & 1){ }
}
//depthと頂点が一致するということは、rootだということ
if(u == v)return u;
//親が同じになるまで同時に登っていく
for(int k = MAX_LOG_V-1; k >= 0; k--){
if(parentku != parentkv){ }
}
}
int main() {
int V;
cin>>V;
rep(i,V-1){
int x,y;
cin>>x>>y;
x--;y--;
}
init(V);
int Q;
cin>>Q;
rep(i,Q){
int a,b;
cin>>a>>b;
a--;b--;
int lcaq = lca(a,b);
int ans = deptha + depthb - 2 * depthlcaq + 1; cout<<ans<<endl;
}
}