$$\Large\texttt{My Blog}$$


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

#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;
}