傳送門
文章目錄
題意
思路：
照例，先考慮不加邊怎么做。由于可以經(jīng)過重復(fù)的邊或點，設(shè)aaa與bbb之間長度為lenlenlen，那么需要len<=klen<=klen<=k并且還需要(k?len)mod2==0(k-len) \bmod 2==0(k?len)mod2==0，因為他可以到終點的時候來回走一個偶數(shù)長度。
那么加上一條邊有什么用呢？由于上面是(k?len)mod2==0(k-len) \bmod 2==0(k?len)mod2==0的時候才符合條件，那么我們多加一條邊極有可能就是改變其奇偶性，事實上也確實是這樣的。
下面有三種走法：
(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
依次求出他們的長度按照上面的方式檢查即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int depth
[N
],fa
[N
][20];
vector
<int>v
[N
];void dfs(int u
,int f
)
{fa
[u
][0]=f
;depth
[u
]=depth
[f
]+1;for(int i
=1;i
<=18;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 i
=18;i
>=0;i
--)if(depth
[fa
[a
][i
]]>=depth
[b
])a
=fa
[a
][i
];if(a
==b
) return a
;for(int i
=18;i
>=0;i
--)if(fa
[a
][i
]!=fa
[b
][i
]) a
=fa
[a
][i
],b
=fa
[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 len
=get(a
,b
);if(len
<=k
&&(k
-len
)%2==0) return true;len
=get(a
,x
)+1+get(y
,b
);if(len
<=k
&&(k
-len
)%2==0) return true;len
=get(a
,y
)+1+get(x
,b
);if(len
<=k
&&(k
-len
)%2==0) return true;return false;
}int main()
{
scanf("%d",&n
);for(int i
=1;i
<=n
-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;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #620 (Div. 2) E. 1-Trees and Queries 思维 + LCA的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
