Loading...

洛谷 P1600 天天爱跑步

check评论:0 条 remove_red_eye浏览量:52 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-14

QAQ好毒瘤的D1T2,awsl

原题链接

  • 题目描述
描述不出来,看题吧(
  • 题目分析

考虑如果一个人对某一个观测者有贡献的情况

首先可以把一段路$s-t$拆成$s-lca$,$lca-t$分别考虑

在上行段中,$dep[i]+w[i]=dep[s]$时有贡献,考虑对每个深度开一颗线段树统计答案,因为只考虑经过一个点的路径,显然可以差分完成

在下行段中,$dep[s]-2*dep[lca]=w[i]-dep[i]$,此时同理

要注意的是,差分时$lca$只能算一次,所以一次差分在$fa[lca]$处$-1$,一次在$lca$处$-1$

然后就做完了QwQ

代码实现

#include <bits/stdc++.h>
using namespace std;
int fa[300010],head[300010],top[300010],dep[300010],siz[300010],son[300010],tot;
int n,m,w[300010],s[300010],t[300010],cnt,sum[2600010],ls[2600010],rs[2600010];
int in[300010],out[300010],qwq[300010],rans[300010],rt[2600010];
struct edge
{
    int next,to;
}e[600010];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs1(int u)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;    
        }    
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
        {
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;
    in[u]=++tot;
    if(son[u])
    {
        dfs2(son[u],tp);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u]||v==son[u])
        {
            continue;
        }
        dfs2(v,v);
    }
    out[u]=tot;
}
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]];
    }
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    return y;
}
void update(int &o,int lf,int rg,int w,int x)
{
    if(!w)
    {
        return ;
    }
    if(!o)
    {
        o=++tot;
    }
    sum[o]+=x;
    if(lf==rg)
    {
        return ;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        update(ls[o],lf,mid,w,x);
    }
    if(mid<w)
    {
        update(rs[o],mid+1,rg,w,x);
    }
}
int query(int o,int lf,int rg,int l,int r)
{
    if(!o)
    {
        return 0;
    }
    if(l<=lf&&rg<=r)
    {
        return sum[o];    
    } 
    int mid=(lf+rg)>>1,ans=0;
    if(l<=mid)
    {
        ans+=query(ls[o],lf,mid,l,r);
    }
    if(mid<r)
    {
        ans+=query(rs[o],mid+1,rg,l,r);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dep[1]=1;
    dfs1(1);
    dfs2(1,1);
    tot=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&s[i],&t[i]);
        qwq[i]=lca(s[i],t[i]);
        update(rt[dep[s[i]]],1,n,in[s[i]],1);
        update(rt[dep[s[i]]],1,n,in[fa[qwq[i]]],-1);
    }
    for(int i=1;i<=n;i++)
    {
        int nowdep=w[i]+dep[i];
        rans[i]+=query(rt[nowdep],1,n,in[i],out[i]);
    }
    memset(sum,0,sizeof(sum)),tot=0;
    memset(ls,0,sizeof(ls)),memset(rs,0,sizeof(rs));
    memset(rt,0,sizeof(rt));
    for(int i=1;i<=m;i++)
    {
        int nowdep=dep[s[i]]-dep[qwq[i]]*2+2*n;
        update(rt[nowdep],1,n,in[t[i]],1);
        update(rt[nowdep],1,n,in[qwq[i]],-1);
    }
    for(int i=1;i<=n;i++)
    {
        int nowdep=w[i]-dep[i]+2*n;
        rans[i]+=query(rt[nowdep],1,n,in[i],out[i]);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<rans[i]<<" ";
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名