洛谷1600 天天爱跑步

Luogu

LOJ

分析

脑子不够,数据结构来凑

我们把每个人的路径拆成上行($s\to lca$)和下行($lca\to t$)两部分。

先考虑上行部分,如果一个人能被 $i$ 点的观察员观察到则有 $dep_s-dep_i=w_i$,移项得到 $dep_s=w_i+dep_i$。

再考虑下行部分,如果一个人能被 $i$ 点的观察员观察到则有 $dis(s,t)-dep_t+dep_i=w_i$,移项得到 $dis(s,t)-dep_t=w_i-dep_i$。

我们可以开两类线段树,每类线段树有 $n$ 棵,其中第一类维护上行路径,第二类维护下行路径。

具体的,对于每条路径 $s\to t$,在第一类线段树中的第 $dep_s$ 棵上将 $s\to lca$ 路径上所有点加 $1$,在第二类线段树中的第 $dis(s,t)-dep_t$ 棵上将 $lca\to t$ 的所有点加 $1$。但是这样子 $lca$ 会被算 $2$ 次,因此随便在一棵线段树上把 $lca$ 减 $1$ 即可。

这样子的话,我们只需要在第一类线段树中的第 $w_i+dep_i$ 棵中查询 $i$ 位置的权值,就可以得到上行路径被 $i$ 观察到的次数了;再在第二类线段树中的第 $w_i-dep_i$ 棵中查询 $i$ 位置的权值,就可以得到下行路径被 $i$ 观察到的次数了。两者相加即可得到答案。

然后线段树空间开不下,动态开点即可;在对第二类线段树访问时可能出现负下标,需要向右平移。

代码比运输计划还短

代码

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

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=299998+10,SIZE=300000;

int n,m,w[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dep[N],fa[N],sz[N],hson[N],top[N];
int dfn[N],tim=0;
inline void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
inline int getdis(int u,int v) {
    return dep[u]+dep[v]-(dep[getlca(u,v)]<<1);
}

#define ls ch[o][0]
#define rs ch[o][1]
int rt1[SIZE<<1],rt2[SIZE<<1],tot=0;
int ch[N*30][2],sumv[N*30],addv[N*30];
inline void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; }
inline void pushdown(int o,int l,int r) {
    if (addv[o]) { int mid=(l+r)>>1;
        if (!ls) ls=++tot;
        addv[ls]+=addv[o],sumv[ls]+=(mid-l+1)*addv[o];
        if (!rs) rs=++tot;
        addv[rs]+=addv[o],sumv[rs]+=(r-mid)*addv[o];
        addv[o]=0;
    }
}
inline void modify(int& o,int l,int r,int ql,int qr,int w) {
    if (!o) o=++tot;
    if (ql<=l&&r<=qr) { addv[o]+=w,sumv[o]+=(r-l+1)*w; return; }
    int mid=(l+r)>>1; pushdown(o,l,r);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline int query(int o,int l,int r,int p) {
    if (!o) return 0;
    if (l==r) return sumv[o];
    int mid=(l+r)>>1,res=0; pushdown(o,l,r);
    if (p<=mid) res=query(ls,l,mid,p);
    else res=query(rs,mid+1,r,p);
    pushup(o); return res;
}
#undef ls
#undef rs

inline void modify(int s,int t) {
    int lca=getlca(s,t),ds=dep[s],dt=getdis(s,t)-dep[t]+SIZE;
    while (top[s]!=top[lca]) {
        modify(rt1[ds],1,n,dfn[top[s]],dfn[s],1);
        s=fa[top[s]];
    }
    modify(rt1[ds],1,n,dfn[lca],dfn[s],1);
    while (top[t]!=top[lca]) {
        modify(rt2[dt],1,n,dfn[top[t]],dfn[t],1);
        t=fa[top[t]];
    }
    modify(rt2[dt],1,n,dfn[lca]+1,dfn[t],1);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    for (re int i=1;i<=n;++i) w[i]=read();
    for (re int i=1,s,t;i<=m;++i) s=read(),t=read(),modify(s,t);
    for (re int i=1;i<=n;++i) {
        int ans1=query(rt1[w[i]+dep[i]],1,n,dfn[i]);
        int ans2=query(rt2[w[i]-dep[i]+SIZE],1,n,dfn[i]);
        printf("%d%c",ans1+ans2," \n"[i==n]);
    }
    return 0;
}
最后修改:2019 年 11 月 06 日 02 : 35 PM

发表评论