2018.08.09 bzoj4719: [Noip2016]天天爱跑步（树链剖分）

传送门

话说开始上文化课之后写题时间好少啊。

这道题将一个人的跑步路线拆成s->lca,lca->t，然后对于第一段上坡路径要经过的点，当前这个人能对它产生贡献当且仅当dep[s]-dep[i]==w[i]，对于第二段路径同理能产生贡献当且仅当dep[t]-dep[i]==dis(s,t)-w[i]，同时需要看lca有没有被算重，这几个东西一看就可以差分，但差分不仅不好想也不好写，我就用数据结构来代替啦。

其实就是树链剖分+动态开点。

代码：

#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n,m;
int hson[N],num[N],ans[N],first[N],top[N],dep[N],fa[N],siz[N],dfn=0,tot=0,cnt=0,rt[N*3];
struct Node{int l,r,sum;}T[N*30];
struct node{int v,next;}e[N<<1];
int s[N],t[N],w[N],lca[N];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline int read(){
    int ret=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
    return ret;
}
inline void dfs1(int p){
    siz[p]=1,hson[p]=0;
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa[p])continue;
        fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
        if(siz[v]>siz[hson[p]])hson[p]=v;
    }
}
inline void dfs2(int p,int tp){
    top[p]=tp,num[p]=++dfn;
    if(hson[p])dfs2(hson[p],tp);
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v!=hson[p]&&v!=fa[p])dfs2(v,v);
    }
}
inline void update(int&p,int l,int r,int k,int v){
    if(!p)p=++tot,T[p].l=T[p].r=T[p].sum=0;
    T[p].sum+=v;
    if(l==r)return;
    int mid=l+r>>1;
    if(k<=mid)update(T[p].l,l,mid,k,v);
    else update(T[p].r,mid+1,r,k,v);
}
inline int query(int p,int l,int r,int ql,int qr){
    if(!p)return 0;
    if(ql<=l&&r<=qr)return T[p].sum;
    int mid=l+r>>1;
    if(qr<=mid)return query(T[p].l,l,mid,ql,qr);
    if(ql>mid)return query(T[p].r,mid+1,r,ql,qr);
    return query(T[p].l,l,mid,ql,mid)+query(T[p].r,mid+1,r,mid+1,qr);
}
inline int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i)w[i]=read();
    dfs1(1),dfs2(1,1);
    for(int i=1;i<=m;++i){
        s[i]=read(),t[i]=read();
        lca[i]=LCA(s[i],t[i]);
        if(dep[s[i]]-dep[lca[i]]==w[lca[i]])--ans[lca[i]];
        update(rt[dep[s[i]]],1,n,num[s[i]],1);
        if(fa[lca[i]])update(rt[dep[s[i]]],1,n,num[fa[lca[i]]],-1);
    }
    for(int i=1;i<=n;++i)ans[i]+=query(rt[w[i]+dep[i]],1,n,num[i],num[i]+siz[i]-1);
    memset(rt,0,sizeof(rt)),tot=0;
    for(int i=1;i<=m;++i){
        update(rt[n*2+dep[s[i]]-2*dep[lca[i]]],1,n,num[t[i]],1);
        if(fa[lca[i]])update(rt[n*2+dep[s[i]]-2*dep[lca[i]]],1,n,num[fa[lca[i]]],-1);
    }
    for(int i=1;i<=n;++i)ans[i]+=query(rt[w[i]-dep[i]+n*2],1,n,num[i],num[i]+siz[i]-1);
    for(int i=1;i<=n;++i)cout<<ans[i]<<' ';
    return 0;
}

巴特西

2018.08.09 bzoj4719: [Noip2016]天天爱跑步（树链剖分）

最新文章

热门文章