首页 > 其他分享 >[ABC267F] Exactly K Steps 题解

[ABC267F] Exactly K Steps 题解

时间:2023-12-26 21:34:17浏览次数:43  
标签:dist int 题解 Exactly dfs dep Steps include

[ABC267F] Exactly K Steps 题解

思路

首先发现,如果对于查询 \((u, k), k > 0\) 可行,那么对于 \((u, k - 1)\) 也一定可行,因为往回走一步就可以了,所以对于一个点可以找到离它最远的点,根据直径的结论,这个点一定是直径的端点之一。

为了方便做,以直径的端点之一为根,然后写一个 K 级祖先稍微分讨一下就搞好了。

时间复杂度:\(O(n\log n + q\log n)\)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
//#define int long long

using namespace std;

const int N = 2e5 + 10;

int n, q;
vector<int> g[N];

int dist[2][N], A, B, f[N][20], dep[N];
void dfs(int dist[], int u, int fa) {
     f[u][0] = fa;
     for(int i = 1; i < 20; i ++)
          f[u][i] = f[f[u][i - 1]][i - 1];
     for(auto v : g[u]) {
          if(v == fa) continue;
          dist[v] = dist[u] + 1;
          dep[v] = dep[u] + 1;
          dfs(dist, v, u);
     }
}
int LCA(int a, int b) {
     if(dep[a] < dep[b]) swap(a, b);
     for(int i = 19; i >= 0; i --)
          if(dep[f[a][i]] >= dep[b])
               a = f[a][i];
     if(a == b) return a;
     for(int i = 19; i >= 0; i --)
          if(f[a][i] != f[b][i]) 
               a = f[a][i],
               b = f[b][i];
     return f[a][0];
}
int jump(int u, int k) {
     for(int i = 20; i >= 0; i --)
          if(k >= (1 << i)) u = f[u][i], k -= (1 << i);
     return u;
}
signed main() {
     ios::sync_with_stdio(0), cin.tie(0);
     cin >> n;
     for(int i = 1, a, b; i < n; i ++) {
          cin >> a >> b;
          g[a].push_back(b), g[b].push_back(a);
     } cin >> q;
     dfs(dist[0], 1, 1);
     for(int i = 1; i <= n; i ++) if(dist[0][i] > dist[0][A]) A = i;
     dep[A] = 0, dfs(dist[1], A, A);
     for(int i = 1; i <= n; i ++) if(dist[1][i] > dist[1][B]) B = i;
     dist[0][B] = 0;
     dfs(dist[0], B, 0), 
     dist[1][A] = 0, dep[A] = 0;
     dfs(dist[1], A, 0);
     for(int i = 1, x, y; i <= q; i ++) {
          cin >> x >> y;
          if(max(dist[0][x], dist[1][x]) < y) cout << -1 << '\n';
          else {
               if(dep[x] >= y) {
                    cout << jump(x, y) << '\n';
                    continue;
               }
               int lca = LCA(B, x);
               y -= dep[x] - dep[lca];
               cout << jump(B, dep[B] - dep[lca] - y) << '\n';
          }
     }
     return 0;
}

标签:dist,int,题解,Exactly,dfs,dep,Steps,include
From: https://www.cnblogs.com/MoyouSayuki/p/17929408.html

相关文章

  • 【CF30E】Tricky and Clever Password 题解(manacher + exKMP)
    manacher+exKMP+二分。感觉是最粗暴的方法,想出来之后自己硬莽了4k,荣获题解区最长。Solution约定:下文所提及到的所有的回文串,均指奇长度回文串。显然把题目拆成两个部分,中间的回文串,以及两边相同的连续子串。考虑一下从哪个入手比较好。忘记是咋想的了,易得从两边相同......
  • [SNOI2019] 网络 题解
    [SNOI2019]网络题解最喜欢这道题。简要题意给一颗\(n\)个节点的树和一个参数\(d\),定义两个节点\(x,y\)之间的距离为\(x\)到\(y\)的简单路径上的边数。定义一个树上连通块的权值为连通块中任意两点的距离之和。定义一个树上连通块的直径为连通块中任意两点距离的最......
  • CF1887C Minimum Array 题解
    Problem-1887C-CodeforcesMinimumArray-洛谷有点被降智了/ll首先区间修改显然先转化成差分序列单点修改。显然对于相同的操作序列,\(a_i\)的取值对答案无影响,因此我们可以先让\(a_i\)全部取\(0\),最后再加回来即可假如说操作到某一时刻,\(a_i\)的值中第一个......
  • 洛谷B3647 【模板】Floyd 题解 floyd算法 求 多源多汇最短路
    题目链接:https://www.luogu.com.cn/problem/B3647floyd算法:https://oi-wiki.org/graph/shortest-path/#floyd-算法示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=101;intn,m,f[maxn][maxn];intmain(){scanf("%d%d",&n......
  • [题解]CF1811D Umka and a Long Flight
    思路假设原题目中的\(n\)在本文中为\(num\),则原长方形的长\(m=f_{num+1}\)和宽\(n=f_{num}\)。显然对于最初始的长方形,显然是要将一个\(f_{num}\timesf_{num}\)的长方形丢进去的,并且要么放最左边,要么放在最右边。因为对于当前的\(m=f_{num+1}=f_{num}+......
  • CF768G The Winds of Winter题解
    我们考虑暴力咋做,每次得到一个森林之后,必定是从最大的树上摘一棵子树,挪到最小的树上,所以此时的答案为\(max(siz_{mx}-x,siz_{mn}+x,siz_{次大值})\),于是发现\(x=\frac{siz_{mx}-siz_{mn}}{2}\)时答案最优,所以只需找到这个值的前驱后继即可我们使用\(\text{multiset}\)实现,......
  • HNOI2017影魔题解
    HNOI2017影魔对于两种贡献,都只用考虑左边第一个比自己大的,和右边第一个比自己大的数,分别记为\(l_i、r_i\)对于询问一,每个数对\((l_i,r_i)\)构成全部情况对于询问二,可以拆分成\(x=l_i\)时,\(y\in[i+1,r_i-1]\),以及\(y=r_i\)时,\(x\in[l_i+1,i-1]\)我们考虑用扫描线......
  • 软件测试/测试开发|selenium NoSuchDriverException问题解决
    前言我们在使用selenium进行web自动化测试时,有时候会遇到NoSuchDriverException的问题,这个异常通常是由于WebDriver无法找到指定的浏览器驱动而引起的。在这篇文章中,我们将讨论NoSuchDriverException的原因以及如何解决这个问题。NoSuchDriverException是什么?NoSuchDriverExce......
  • CF1051C Vasya and Big Integers 题解
    Problem-1051E-CodeforcesVasyaandBigIntegers-洛谷感谢女队提交记录推荐给我的一道题\(Orz\)首先\(O(n^2)\)的\(dp\)是simple的,如果你没看出来你可能是像我一样把题目看错了设\(dp_i\)表示考虑前\(i\)个的方案数,转移枚举长度后比较字典序。虽然看......
  • P6922 [ICPC2016 WF] Longest Rivers 题解
    Description有\(n\)条河和\(m+1\)个交汇处构成一棵以\(0\)号点(即大海)为根的树。每条河有各自的名称。对于一个交汇处,从它流出的干流的名称是流入这个交汇处的各个支流的名称之一。一条河流的长度是以它为名称的河流的长度之和。对于一个可能的命名方案,一条河流的排名等于......