M_sea

CF1110F Nearest Leaf
CodeForcesLuogu分析似乎比较简单...把所有询问离线,当访问一个节点时批量处理关于它的询问。根据题目...
扫描右侧二维码阅读全文
14
2019/05

CF1110F Nearest Leaf

CodeForces

Luogu

分析

似乎比较简单...

把所有询问离线,当访问一个节点时批量处理关于它的询问。

根据题目,每棵子树的编号都是连续的。设 $mx[i]$ 表示 $i$ 子树中的最大的编号。

假设当前在 $u$ ,询问为 $(l,r)$ ,我们用线段树维护到 $u$ 的距离,那么直接查询最小值即可。

当从 $u$ 到 $v$ 时,$v$ 子树内叶子的距离会减少 $w$ , $v$ 子树外叶子的距离会增加 $w$ 。那么直接在线段树上修改即可。

为了避免非叶子节点的影响,应把所有非叶子节点在线段树上的值设为 $\infty$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,m;

//图
struct Edge { int v,w,nxt; } e[N];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

//线段树
struct Segment_Tree {
#define ls (o<<1)
#define rs (o<<1|1)
    ll minv[N<<2],addv[N<<2];
    inline void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
    inline void pushdown(int o) {
        if (addv[o]) {
            minv[ls]+=addv[o],addv[ls]+=addv[o];
            minv[rs]+=addv[o],addv[rs]+=addv[o];
            addv[o]=0;
        }
    }
    inline void modify(int o,int l,int r,int ql,int qr,ll v) {
        if (ql<=l&&r<=qr) { minv[o]+=v,addv[o]+=v; return; }
        int mid=(l+r)>>1;
        pushdown(o);
        if (ql<=mid) modify(ls,l,mid,ql,qr,v);
        if (qr>mid) modify(rs,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline ll query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return minv[o];
        int mid=(l+r)>>1; ll res=2e18;
        pushdown(o);
        if (ql<=mid) res=min(res,query(ls,l,mid,ql,qr));
        if (qr>mid) res=min(res,query(rs,mid+1,r,ql,qr));
        pushup(o); return res;
    }
#undef ls
#undef rs
} T;

//一些信息
int mx[N]; //子树中编号最大的点
ll dis[N];

inline void dfs1(int u,int fa) {
    mx[u]=u;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; dis[v]=dis[u]+w;
        dfs1(v,u); mx[u]=max(mx[u],mx[v]);
    }
}

//计算答案
vector<int> q[N];
int l[N],r[N];
ll ans[N];

inline void dfs2(int u,int fa) {
    for (re int i:q[u]) ans[i]=T.query(1,1,n,l[i],r[i]);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        T.modify(1,1,n,1,n,w),T.modify(1,1,n,v,mx[v],-w-w);
        dfs2(v,u);
        T.modify(1,1,n,1,n,-w),T.modify(1,1,n,v,mx[v],w+w);
    }
}

int main() {
    n=read(),m=read();
    for (re int i=2;i<=n;++i) {
        int f=read(),w=read();
        addEdge(f,i,w);
    }
    dfs1(1,0);
    for (re int i=1;i<=n;++i) {
        if (i==mx[i]) T.modify(1,1,n,i,i,dis[i]);
        else T.modify(1,1,n,i,i,1e18);
    }
    for (re int i=1;i<=m;++i) {
        int u=read(); l[i]=read(),r[i]=read();
        q[u].push_back(i);
    }
    dfs2(1,0);
    for (re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 08 PM

发表评论