高端 网站,上海的重大新闻,销售管理系统业务处理流程,让别人做网站怎样才安全传送门 文章目录题意思路#xff1a;题意 思路#xff1a;
照例#xff0c;先考虑不加边怎么做。由于可以经过重复的边或点#xff0c;设aaa与bbb之间长度为lenlenlen#xff0c;那么需要lenklenklenk并且还需要(k−len)mod20(k-len) \bmod 20(k−len)mod20题意 思路
照例先考虑不加边怎么做。由于可以经过重复的边或点设aaa与bbb之间长度为lenlenlen那么需要lenklenklenk并且还需要(k−len)mod20(k-len) \bmod 20(k−len)mod20因为他可以到终点的时候来回走一个偶数长度。 那么加上一条边有什么用呢由于上面是(k−len)mod20(k-len) \bmod 20(k−len)mod20的时候才符合条件那么我们多加一条边极有可能就是改变其奇偶性事实上也确实是这样的。 下面有三种走法 (1)a−b(1)a-b(1)a−b (2)a−x−y−b(2)a-x-y-b(2)a−x−y−b (3)a−y−x−b(3)a-y-x-b(3)a−y−x−b 依次求出他们的长度按照上面的方式检查即可。
// Problem: E. 1-Trees and Queries
// Contest: Codeforces - Codeforces Round #620 (Div. 2)
// URL: https://codeforces.com/contest/1304/problem/E
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int depth[N],fa[N][20];
vectorintv[N];void dfs(int u,int f)
{fa[u][0]f;depth[u]depth[f]1;for(int i1;i18;i) fa[u][i]fa[fa[u][i-1]][i-1];for(auto x:v[u]) if(x!f) dfs(x,u);
}int lca(int a,int b)
{if(depth[a]depth[b]) swap(a,b);for(int i18;i0;i--)if(depth[fa[a][i]]depth[b])afa[a][i];if(ab) return a;for(int i18;i0;i--)if(fa[a][i]!fa[b][i]) afa[a][i],bfa[b][i];return fa[a][0];
}int get(int a,int b)
{return depth[a]depth[b]-2*depth[lca(a,b)];
}bool check(int x,int y,int a,int b,int k)
{int lenget(a,b);if(lenk(k-len)%20) return true;lenget(a,x)1get(y,b);if(lenk(k-len)%20) return true;lenget(a,y)1get(x,b);if(lenk(k-len)%20) return true;return false;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in-1;i){int a,b; scanf(%d%d,a,b);v[a].pb(b); v[b].pb(a);}dfs(1,0);int q; scanf(%d,q);while(q--){int a,b,x,y,k; scanf(%d%d%d%d%d,x,y,a,b,k);if(check(x,y,a,b,k)) puts(YES);else puts(NO);}return 0;
}
/**/
