description

點擊查看題目

solution

考慮將邊拆分，邊長$\times 2$
然后將$k$步以內可以互相走到的點用并查集合并在一起
同一個連通塊的關鍵點可以相互走到
然后對于詢問的兩個城市，$u$向$v$走$k$步，$v$向$u$走$k$步，然后判斷是不是在同一個連通塊，使用樹上倍增$log$做到
注意兩點距離公共祖先是不是比$k$小
如果是，那么有一方是需要走折線的，就是先走到祖先再往下面另一方走

code

#include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> using namespace std; #define maxn 500005 queue < pair < int, int > > q; vector < int > G[maxn]; int n, k, r, Q; int f[maxn], dep[maxn]; int fa[maxn][20]; bool vis[maxn];void makeSet( int n ) {for( int i = 1;i <= n;i ++ ) f[i] = i; }int find( int x ) {return x == f[x] ? x : f[x] = find( f[x] ); }void bfs() {while( ! q.empty() ) {int u = q.front().first, step = q.front().second;q.pop();if( step == k ) return;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];int fu = find( u ), fv = find( v );f[fv] = fu;if( ! vis[v] ) {vis[v] = 1;q.push( make_pair( v, step + 1 ) );}}} }void dfs( int u, int Fa ) {fa[u][0] = Fa, dep[u] = dep[Fa] + 1;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( v == Fa ) continue;else dfs( v, u );} }int LCA( int u, int v ) {if( dep[u] < dep[v] ) swap( u, v );for( int i = 19;~ i;i -- )if( dep[fa[u][i]] >= dep[v] )u = fa[u][i];if( u == v ) return u;for( int i = 19;~ i;i -- )if( fa[u][i] != fa[v][i] )u = fa[u][i], v = fa[v][i];return fa[u][0]; }int climb( int u, int d ) {for( int i = 0;i < 20;i ++ )if( 1 << i & d ) u = fa[u][i];return u; }int main() {scanf( "%d %d %d", &n, &k, &r );int cnt = n;for( int i = 1, u, v;i < n;i ++ ) {scanf( "%d %d", &u, &v );++ cnt;G[u].push_back( cnt );G[cnt].push_back( u );G[cnt].push_back( v );G[v].push_back( cnt ); }makeSet( cnt );for( int i = 1, key;i <= r;i ++ ) {scanf( "%d", &key );q.push( make_pair( key, 0 ) );vis[key] = 1;}bfs();dfs( 1, 0 );scanf( "%d", &Q );for( int i = 1, s, t;i <= Q;i ++ ) {scanf( "%d %d", &s, &t );int lca = LCA( s, t );int len = dep[s] + dep[t] - ( dep[lca] << 1 );if( len <= ( k << 1 ) ) printf( "YES\n" );else {int u = dep[s] - dep[lca] >= k ? climb( s, k ) : climb( t, len - k );int v = dep[t] - dep[lca] >= k ? climb( t, k ) : climb( s, len - k );if( find( u ) == find( v ) ) printf( "YES\n" );else printf( "NO\n" );}}return 0; }

總結

以上是生活随笔為你收集整理的【CF1307F】Cow and Vacation（并查集+lca倍增）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。