CF Round #620 E 1-Trees and Queries
題意：給你一顆樹，進(jìn)行?次查詢，每次查詢時(shí)在樹上加一條邊，然后問此時(shí)兩點(diǎn)間的距離能否為一個(gè)特定的值?，（能反復(fù)經(jīng)過同一個(gè)節(jié)點(diǎn)或同一條邊）。
基本思路：加了一條邊連接了x，y?以后，a，b兩點(diǎn)間的距離就有三種形式，即 ;然后由于能反復(fù)經(jīng)過同一個(gè)節(jié)點(diǎn)或同一條邊，所以答案一定是上面三種可能 + (k為任意自然數(shù))，所以直接循環(huán)判斷就行，我這里是奇偶形式判斷（不如直接循環(huán)）。 主要知識(shí)上的難點(diǎn)為通過lca快速求樹上兩點(diǎn)間的距離，可以直接套模板。
<pre mdtype="fences" cid="n10" lang="cpp" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include<bits/stdc++.h>
using namespace std;
define ll long long
const int maxn = 3e5+10;
int n, q;
vector<int> G[maxn];
int fa[maxn][21], depth[maxn];
?
?
void dfs(int u, int f){
fa[u][0] = f;
for (int i = 1; i <= 20; i++){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(f != v){
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
}
int lca(int x, int y){
int u = x, v = y;
if(depth[u] < depth[v])
swap(u, v);
for (int i = 20; i >= 0; i--){
if(depth[fa[u][i]] >= depth[v]){
u = fa[u][i];
}
}
if(u == v) return abs(depth[x] - depth[y]);
for (int i = 20; i >= 0; i--){
//if(depth[fa[u][i]] != depth[fa[v][i]]){ //為啥我也不知道...
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return depth[x] + depth[y] - 2 * depth[fa[u][0]];
}
bool check(int x, int y){
return (y>=x) && (x & 1) == (y & 1);
}
int main(){
ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
depth[0] = 0;
dfs(1, 0);
cin >> q;
while(q--){
int x, y, a, b, k;
cin >> x >> y >> a >> b >> k;
if(check(lca(a, b), k) || check(lca(a, x)+lca(y, b) + 1, k) || check(lca(a, y) + lca(x, b) + 1, k)){
cout << "YES" << endl;
}
else
cout << "NO" << endl;
}
return 0;
}</pre>
參考：
