题解 CF1110F 【Nearest Leaf】
Siyuan
2019-02-08 21:36:04
[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-Codeforces-1110F-Nearest-Leaf/)
---
## Description
> 题目链接：[Codeforces 1110F](https://codeforces.com/contest/1110/problem/F)
给你一棵带权有根树，根节点为 $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
```cpp
#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;
}
```