「Codeforces 1110F」Nearest Leaf

Description

题目链接:Codeforces 1110F

给你一棵带权有根树,根节点为 $1​$,且保证每个点的父亲 $p_i<i​$,其中 $(p_i,i)​$ 的边权为 $w_i​$。这棵树有个性质:如果我们 $\text{DFS}​$ 这棵树,对于每个点都递增枚举儿子节点,每访问到一个节点就记录其编号,那么得到的序列刚好为 $1​$ 到 $n​$。

现在有 $q​$ 次询问,每次给出 $v_i,l_i,r_i​$,求从 $v_i​$ 出发到 $[l_i,r_i]​$ 中的其中一个叶子节点的最短距离(保证 $[l_i,r_i]​$ 中至少有一个叶子节点)。

数据范围:$3\le n\le 5\times 10^5​$,$1\le q\le 5\times 10^5​$,$1\le p_i<i​$,$1\le w_i\le 10^9​$


Solution

考虑都没有修改操作,我们可以把询问离线下来。按照询问的节点分类。

我们首先观察一个性质:由于 $\text{DFS}$ 序就是 $1$ 到 $n$,那么意味着每棵子树内的编号都是连续的,记子树 $i$ 内点的最大编号为 $k_i​$。

我们再考虑一个问题:如果从 $u​$ 到达 $v​$(我们记这条边为 $(u,v,w)​$),其中 $v​$ 的深度大于 $u​$,那么到达每个叶子的路径长度会发生什么变化?

  • 对于在 $v​$ 子树内的叶子,到他们的距离减少 $w​$。
  • 其余叶子节点,到他们的距离增加 $w​$。

根据之前的性质,我们发现 $v$ 子树内的节点编号连续,可以直接用线段树修改。具体的修改方法为:我们将线段树内 $[1,n]$ 的节点的值增加 $w$,将 $[v,k_v]$ 的节点的值减少 $2w​$。

为了防止对线段树中非叶子节点的影响,我们应该要将他们的值初始化为 $\text{INF}$,使得无论如何修改都不会影响答案。

这样一来,我们可以得到一个简单的算法流程:

  1. 将 $1$ 到所有叶子节点的距离放到线段树中,非叶子节点的距离定义为 $\text{INF}$。
  2. 直接 $\text{DFS}$ 整棵树,将询问节点为当前节点的询问统计答案。
  3. 枚举当前节点 $u$ 的儿子节点 $v$,在线段树上修改 $[v,k_v]$ 的值并递归求解 $v$ 的值;递归后记得回溯消去影响!

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


Code

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
#include <cstdio>
#include <algorithm>
#include <vector>
#define lson p<<1
#define rson p<<1|1

const int N=5e5+5;
const long long INF=1LL<<60;
int n,m,tot,l[N],r[N],mx[N],lnk[N],ter[N],nxt[N],val[N];
long long seg[N<<2],tag[N<<2],dis[N],ans[N];
std::vector<int> q[N];

void pushup(int p) {
seg[p]=std::min(seg[lson],seg[rson]);
}
void pushdown(int p) {
if(!tag[p]) return;
long long v=tag[p];
seg[lson]+=v,tag[lson]+=v,seg[rson]+=v,tag[rson]+=v,tag[p]=0;
}
void modify(int x,int y,int p,int l,int r,long long v) {
if(x<=l&&r<=y) {
seg[p]+=v,tag[p]+=v;
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) modify(x,y,lson,l,mid,v);
if(mid<y) modify(x,y,rson,mid+1,r,v);
pushup(p);
}
long long query(int x,int y,int p,int l,int r) {
if(x<=l&&r<=y) return seg[p];
pushdown(p);
int mid=(l+r)>>1;
long long ans=INF;
if(x<=mid) ans=std::min(ans,query(x,y,lson,l,mid));
if(mid<y) ans=std::min(ans,query(x,y,rson,mid+1,r));
return ans;
}
void add(int u,int v,int w) {
ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void dfs1(int u) {
mx[u]=u;
for(int i=lnk[u];i;i=nxt[i]) {
int v=ter[i];
dis[v]=dis[u]+val[i];
dfs1(v);
mx[u]=std::max(mx[u],mx[v]);
}
}
void dfs2(int u) {
for(int i:q[u]) ans[i]=query(l[i],r[i],1,1,n);
for(int i=lnk[u];i;i=nxt[i]) {
int v=ter[i],w=val[i];
modify(1,n,1,1,n,w),modify(v,mx[v],1,1,n,-w-w);
dfs2(v);
modify(1,n,1,1,n,-w),modify(v,mx[v],1,1,n,w+w);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=2;i<=n;++i) {
int p,w;
scanf("%d%d",&p,&w),add(p,i,w);
}
dfs1(1);
for(int i=1;i<=n;++i) {
modify(i,i,1,1,n,i==mx[i]?dis[i]:INF);
}
for(int i=1;i<=m;++i) {
int v;
scanf("%d%d%d",&v,&l[i],&r[i]),q[v].push_back(i);
}
dfs2(1);
for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}
0%