F - Exactly K Steps（树的直径 + 倍增）

F - Exactly K Steps

树的直径 + 倍增

分析

首先树的直径没啥好说的…
离一个点u最远的点一定是树的直径的两个端点；

所以我们首先要找一下树的直径，这个简单；
关键是对于每个询问我们要怎么快速找到对应的点？

我们可以利用这个性质：离一个点u最远的点一定是树的直径的两个端点（root1，root2）；
那么可以知道如果这个点存在，u到max_dis(root1, root2)的路径上则一定会有一个点满足；
因此我们可以分别以root1，root2作为树根形成两棵树，然后对于u，在两棵树上往上找距离为k的点；

这个其实是比较难搞的（如果没学过lca的话），说起来我倍增好像是在学lca的时候学的…
我们可以借助倍增，f[u][i]表示u向上跳2^i的距离所能到的点是哪个；

下面考虑怎么预处理出这个数组：
这里设x是u的子节点；
那么f[x][0] = u;
f[x][i] = f[f[x][i-1]][i-1];
即x跳2^i步到的点 = x跳2^(i-1)步所到的点 再跳 2^(i-1)步；
(2^i = 2^(i-1) * 2)(跳两次i-1)；

那么对于每个询问：u，k；
我们直接从大到小看i，考虑是否k >= 2^i;
如果可以跳，则u = f[u][i]，一直往上跳，然后k -= 2^i；

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
#include <random>
#include<bitset>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define dre(x) scanf("%lf",&x)
#define ddre(a,b) scanf("%lf %lf",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
// #define double long double
// typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 3e5 + 7;
const int N = 5e5 + 7;
const int M = 5e5 + 7;
const int mod = 19980829;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

vector<int> g[maxn];
int dep[3][maxn];
int f[3][maxn][20];
int n;
int vis[maxn];
int root1,root2;

void dfs(int u,int fa,int p)
{
	for(auto x : g[u])
	{
		if(fa == x) continue;
		
		dep[p][x] = dep[p][u] + 1;
		
		dfs(x,u,p);
	}
}

void sol()	//求树的直径
{
	dfs(1,-1,0);
	int mx = 0;
	for(int i=1;i<=n;i++)
		if(dep[0][i] > mx)
		{
			mx = dep[0][i];
			root1 = i;
		}
	
	rep(i,1,n) dep[0][i] = 0;
	
	dfs(root1,-1,0);
	mx = 0;
	for(int i=1;i<=n;i++)
		if(dep[0][i] > mx)
		{
			mx = dep[0][i];
			root2 = i;
		}
}

void bfs(int root,int p)  //预处理depth[] 和 f[][]数组, 从根开始向下更新 
{
    memset(vis,0,sizeof vis);

    queue<int> q;
    q.push(root);

    while(q.size())
    {
        int no = q.front(); //父节点 
        q.pop();

		vis[no] = 1;
		
        for(int j : g[no])    //子节点 
        {
        	if(vis[j]) continue;
        	
        	f[p][j][0] = no;   //子节点跳一步到父节点
            for(int k=1; k<20; k++)    //枚举往上跳2^k步
               f[p][j][k] = f[p][f[p][j][k-1]][k-1];    //2^k = 2^(k-1) + 2^(k-1)
        	
        	q.push(j);
        }
    }
}

void solve()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	sol();
	
	dfs(root1,-1,1);
	dfs(root2,-1,2);
	
	bfs(root1,1);
	bfs(root2,2);
	
	int q;
	cin>>q;
	while(q--)
	{
		int u,k;
		cin>>u>>k;
		
		if(dep[1][u] < k && dep[2][u] < k)
		{
			cout<<-1<<'\n';
			continue;
		}
		
		int mx = dep[1][u] > dep[2][u] ? 1 : 2;
		
		int i = 19;
		while(i >= 0)
		{
		    int dis = pow(2,i);
		    while(k >= dis)
		    {
		        u = f[mx][u][i];
		        k -= pow(2,i);
		    }
		    i--;
		}
		
		cout<<u<<'\n';
	}
}

int main()
{
//	IOS;
	
	int t;
//	ire(t);
//	cin>>t;
	t = 1;
	while(t--)
	{
		solve();
	}
    	
 	return 0;
}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199