E. 1-Trees and Queries
Problem Restatement
给出一个(n)个节点的树，每次询问，连结(x)与(y)节点，问(a)到(b)节点是否存在一条路径，使得长度为(k)（点和边 可重复走）。
(( 3 le n le 10^5, 1 le q le 10^5))
Solution
如果没连结(x)和(y)节点，则(a)到(b)之间的最短路是唯一的，而且由于树没有环，所以在最短路的基础上，只能两个节点之间来回“蹭”（蹭就是走到终点之后，与相邻两个点来回走），所以如果求的最短路为( ext{dist}(a,b))，那么唯有当( ext{dist}(a,b)leq k)，而且(2|k- ext{dist}(a,b))时，才可以成立。
考虑到目前连结了(x,y)，还是考虑(a)到(b)的最短路。我们可以分出3种情况。
1、不经过( ext {edge}(x,y))的最短路。即( ext{dist}(a,b))。
2、先从(a)到(x)，经过( ext {edge}(x,y))，然后从(y)到(b)。即( ext{dist}(a,x)+1+ ext{dist}(y,b))。
3、先从(b)到(x)，经过( ext {edge}(x,y))，然后从(y)到(a)。即( ext{dist}(b,x)+1+ ext{dist}(y,a))。
可以证明最短路一定在这三种情况之中，而且任何的路都是从这三条路之后重复“蹭”出去的。
（这里证明我没有想到简易证明，倒是可以通过分类讨论( ext {edge}(x,y))的位置，比较繁琐。另，证明中其实成环之和的讨论比较特别，要用到奇偶分析。这里留给读者当课后习题。）
总之，如果不能被这三种情况“蹭”出来，那么就是无法构造的。
Code
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXLN 20
using namespace std;
struct edge{
int to,next;
}e[MAXN<<1];
int tot,head[MAXN];
void add(int x,int y){
tot++;
e[tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
int dep[MAXN],lgd[MAXN],st[MAXN][MAXLN];
void dfs(int cur,int fa){
dep[cur]=dep[fa]+1;
st[cur][0]=fa;
for(lgd[cur]=1;(1<<lgd[cur])<=dep[cur];lgd[cur]++)
st[cur][lgd[cur]]=st[st[cur][lgd[cur]-1]][lgd[cur]-1];
for(int p=head[cur];p;p=e[p].next){
if(e[p].to==fa) continue;
dfs(e[p].to,cur);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=0;dep[x]-dep[y];i++)
if((dep[x]-dep[y])&(1<<i)) x=st[x][i];
if(x==y) return x;
for(int i=lgd[x];i>=0;i--)
if(st[x][i]!=st[y][i])
x=st[x][i], y=st[y][i];
return st[x][0];
}
void solve(){
int n,q;
scanf("%d", &n);
tot=0;
memset(head+1,0,n*sizeof(head[0]));
for(int i=1;i<n;i++){
int f,g;
scanf("%d %d", &f, &g);
add(f,g);
add(g,f);
}
dep[0]=0;
dfs(1,0);
scanf("%d", &q);
for(int i=1;i<=q;i++){
int x,y,a,b,k,ax,ay,ab,bx,by;
scanf("%d %d %d %d %d", &x, &y, &a, &b, &k);
ab=dep[a]+dep[b]-2*dep[lca(a,b)];
if(ab<=k && ((ab-k)&1)==0){
printf("YES
");
continue;
}
ax=dep[a]+dep[x]-2*dep[lca(a,x)];
by=dep[b]+dep[y]-2*dep[lca(b,y)];
if(ax+by+1<=k && ((ax+by+1-k)&1)==0){
printf("YES
");
continue;
}
ay=dep[a]+dep[y]-2*dep[lca(a,y)];
bx=dep[b]+dep[x]-2*dep[lca(b,x)];
if(ay+bx+1<=k && ((ay+bx+1-k)&1)==0){
printf("YES
");
continue;
}
printf("NO
");
}
}
int main(){
int T=1;
// scanf("%d", &T);
while(T--){
solve();
}
return 0;
}