CF Round #620 E 1-Trees and Queries

题意：给你一颗树，进行次查询，每次查询时在树上加一条边，然后问此时两点间的距离能否为一个特定的值，（能反复经过同一个节点或同一条边）。

基本思路：加了一条边连接了x，y以后，a，b两点间的距离就有三种形式，即 ;然后由于能反复经过同一个节点或同一条边，所以答案一定是上面三种可能 + (k为任意自然数)，所以直接循环判断就行，我这里是奇偶形式判断（不如直接循环）。主要知识上的难点为通过lca快速求树上两点间的距离，可以直接套模板。

<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>

参考：

CF Round #620 E [1-Trees and Queries]

CF Round #620 E 1-Trees and Queries

define ll long long