链接
https://ac.nowcoder.com/acm/problem/13331
题意
在一个树形图中，每个节点都有一个权值
现在有 $q$ 次询问，每次从节点u前往节点 $v$，保证 $v$ 在 $u$ 到的根节点的最短路径上
每次出发前你有个权值为 $c$ 的起始权值，如果到达节点的权值大于你拥有的权值，那么会强制更新你拥有的权值
问每次询问你会更新几次你拥有的权值
思路
题意中表示如果你访问到的节点的权值大于你拥有的权值，你必须更新你的权值
设 $f[i][j]$ 为从节点 $i$ 往上走，更新权值的第 $2^j$ 个节点
显然，我们必须先求出 $f[i][0]$，记 $i$ 的父亲节点为 $fa$
当 $fa$ 比 $i$ 大：$f[i][0]=fa$
当 $fa$ 不比 $i$ 大：我们可以枚举 $fa$ 的 $2^k$ 辈祖先（$k$从大到小枚举），若 $f[fa][k]$ 的权值不大于 $i$，则让 $fa$ 向上走 $2^k$ 步，继续枚举，若 $f[fa][k]$ 的权值大于 $i$，则让 $2^k$ 减半，重新比较，最终 $fa$ 再往上走一步就是第一个大于 $i$ 的节点，$f[i][0]=f[fa][0]$
求完 $f$ 数组，我们得到了一个父亲节点必大于孩子节点的树形图
接下来我们考虑如果起始权值为 $u$ 的权值，如何求解
显然，我们只需要在新图中从 $u$ 向上倍增，枚举 $k$（$k$从大到小枚举），若 $f[u][k]$ 的深度大于等于 $v$，则让 $u$ 向上走 $2^k$ 步，答案即是总共走了多少步
最后考虑如果起始权值为 $c$，如何求解
我们只需要在求 $f$ 数组前新建立一个权值为 $c$ 的节点 $x$，使其父亲节点为 $u$ ，而我们每次询问由从 $u$ 到 $v$ 转化为从 $x$ 到 $v$
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N=100010;
int n,q;
vector<int>edge[N*2];
int f[N*2][20];
int w[N*2],depth[N*2];
int to[N];
void dfs(int u,int fa) {
int x=fa;
for(int i=18;i>=0;i--)
if(f[x][i]&&w[f[x][i]]<=w[u])
x=f[x][i];
if(w[x]>w[u]) f[u][0]=x;
else f[u][0]=f[x][0];
for(int i=1;i<=18;i++) f[u][i]=f[f[u][i-1]][i-1];
depth[u]=depth[fa]+1;
for(auto v:edge[u]) {
if(v==fa) continue;
dfs(v,u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
edge[u].pb(v);
edge[v].pb(u);
}
for(int i=n+1;i<=n+q;i++) {
int u,v,c;
cin>>u>>v>>c;
edge[i].pb(u);
edge[u].pb(i);
w[i]=c;
to[i-n]=v;
}
dfs(1,0);
for(int i=1;i<=q;i++) {
int u=i+n,v=to[i];
int res=0;
for(int i=18;i>=0;i--) {
if(depth[f[u][i]]>=depth[v]) res+=(1<<i),u=f[u][i];
}
cout<<res<<endl;
}
return 0;
}
|