题意：
给你一棵树。
每次询问，在x和y顶点之间添加了一条边后，如果存在一条路径，该路径恰好包含从a到b的k条边，可以保证原始树不存在x和y之间的边，路径可以经过相同的顶点和边。每个查询相互独立。
题解：
可以推出有三种可能的路径。
a->b
a->x->y->b
a->y->x->b
求出这三种路径的距离，有一条和k的奇偶性相同，就输出YES。
求路径需要套一个LCA倍增算法的模板。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+14; int N,Q; int father[18][maxn]; int h[maxn]; vector<int> g[maxn]; void dfs (int x) { for (int i=0;i<g[x].size();i++) { int v=g[x][i]; if (v==father[0][x]) continue; father[0][v]=x; h[v]=h[x]+1; dfs(v); } } int lca (int x,int y) { if (h[x]<h[y]) swap(x,y); for (int i=17;i>=0;i--) if (h[x]-h[y]>>i) x=father[i][x]; if (x==y) return x; for (int i=17;i>=0;i--) { if (father[i][x]!=father[i][y]) { x=father[i][x]; y=father[i][y]; } } return father[0][x]; } int getDis (int x,int y) { return h[x]+h[y]-h[lca(x,y)]*2; } bool check (int x,int y) { return y>=x&&x%2==y%2; } int main () { scanf("%d",&N); for (int i=1;i<N;i++) { int a,b; scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } dfs(1); for (int i=1;i<=17;i++) { for (int j=1;j<=N;j++) father[i][j]=father[i-1][father[i-1][j]]; } scanf("%d",&Q); for (int i=0;i<Q;i++) { int x,y,a,b,k; scanf("%d%d%d%d%d",&x,&y,&a,&b,&k); if (check(getDis(a,b),k)|| check(getDis(a,x)+getDis(y,b)+1,k)|| check(getDis(a,y)+getDis(x,b)+1,k)) printf("YES\n"); else printf ("NO\n"); } return 0; }
Codeforces Round #620 Div2E 1-Trees and Queries
原文：https://www.cnblogs.com/zhanglichen/p/12425536.html