「Codeforces 1110F」Nearest Leaf

发表于 | | 阅读次数:
字数统计: 1.1k 字

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%