【NOIP 2016】Day1 T2 天天爱跑步

Author Avatar
洛水·锦依卫 1月 25, 2019

【NOIP 2016】Day1 T2 天天爱跑步

题面

题目描述

小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一棵包含 $ n $ 个结点和 $ n - 1 $ 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 $ 1 $ 到 $ n $ 的连续正整数。

现在有 $ m $ 个玩家,第 $ i $ 个玩家的起点为 $ S_i $,终点为 $ T_i $。每天打卡任务开始时,所有玩家在第 $ 0 $ 秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去,跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)

小 C 想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点 $ j $ 的观察员会选择在第 $ W_j $ 秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第 $ W_j $ 秒也正好到达了结点 $ j $。小 C 想知道每个观察员会观察到多少人?

注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点 $ j $ 作为终点的玩家:若他在第 $ W_j $ 秒前到达终点,则在结点 $ j $ 的观察员不能观察到该玩家;若他正好在第 $ W_j $ 秒到达终点,则在结点 $ j $ 的观察员可以观察到这个玩家。

输入格式

第一行有两个整数 $ n $ 和 $ m $。其中 $ n $ 代表树的结点数量,同时也是观察员的数量,$ m $ 代表玩家的数量。

接下来 $ n - 1 $ 行每行两个整数 $ u $ 和 $ v $,表示结点 $ u $ 到结点 $ v $ 有一条边。

接下来一行 $ n $ 个整数,其中第 $ i $ 个整数为 $ W_i $,表示结点 $ i $ 出现观察员的时间。

接下来 $ m $ 行,每行两个整数 $ S_i $ 和 $ T_i $,表示一个玩家的起点和终点。

对于所有的数据,保证 $ 1 \leq S_i, T_i \leq n, 0 \leq W_j \leq n $。

输出格式

输出一行 $ n $ 个整数,第 $ j $ 个整数表示结点 $ j $ 的观察员可以观察到多少人。

样例输入输出

样例输入 1

6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6

样例输出 1

2 0 0 1 1 1

样例解释 1

对于 $ 1 $ 号点,$ W_1 = 0 $,故只有起点为 $ 1 $ 号点的玩家才会被观察到,所以玩家 1 和玩家 2 被观察到,共 $ 2 $ 人被观察到。
对于 $ 2 $ 号点,没有玩家在第 $ 2 $ 秒时在此结点,共 $ 0 $ 人被观察到。
对于 $ 3 $ 号点,没有玩家在第 $ 5 $ 秒时在此结点,共 $ 0 $ 人被观察到。
对于 $ 4 $ 号点,玩家 $ 1 $ 被观察到,共 $ 1 $ 人被观察到。
对于 $ 5 $ 号点,玩家 $ 2 $ 被观察到,共 $ 1 $ 人被观察到。
对于 $ 6 $ 号点,玩家 $ 3 $ 被观察到,共 $ 1 $ 人被观察到。

样例输入 2

5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5

样例输出 2

1 2 1 0 1

说明

测试点 $ 1 \sim 2 $:$ n = m = 991 $,所有人的起点等于自己的终点,即 $ S_i = T_i $;
测试点 $ 3 \sim 4 $:$ n = m = 992 $,$ W_j = 0 $;
测试点 $ 5 $:$ n = m = 993 $;
测试点 $ 6 \sim 8 $:$ n = m = 99994 $,树退化成一条链,对于 $ 1 \leq i < n $,$ i $ 与 $ i + 1 $ 有边;
测试点 $ 9 \sim 12 $:$ n = m = 99995 $,$ S_i = 1 $;
测试点 $ 13 \sim 16 $:$ n = m = 99996 $,$ T_i = 1 $;
测试点 $ 17 \sim 19 $:$ n = m = 99997 $;
测试点 $ 20 $:$ n = m = 299998 $。

考点

$LCA$ ,桶 。

思路

首先是看看数据范围的时候,嗯 …… 讲真 $3e5$ 的数据令人一下想到我们必须用 $O(nlog_2n)$ 或者 $O(n)$ 级别的算法或数据结构维护答案,当然,有树上路径的题目就会有 $LCA$ ,那么 $log$ 是必定有的了 = =。

接着我们看看询问们,$emm$ …… 树上统计符合一定距离要求的其他点,这很显然就是用桶来计数就对了。

那么我们来考虑所谓的用桶计数。用桶计数的关键点是:找到询问与当前统计点的等式。

那么我们来思考一下,对于每个询问,它和统计点的等式是什么呢 ?很显然,如果这条路径经过统计点,且起点与统计点距离等于统计点的 $w$,那么这个询问对统计点的贡献就是 $1$。

但是这个等式并不具有普遍性,因为统计点相对于每个路径的起点都是不方便快速计算的,这样是 $n^2$ 的。那么我们想想还有什么办法?深度啊!对于两点之间的距离不是可以利用深度表示吗?

那么我们来考虑关于深度的等式。这个当然分为两种情况:统计点在 $S$ 到 $lca$ 的路径上与统计点在 $lca$ 到 $T$ 的路径上。设统计点为点 $i$ ,那么接着我们来列出具体等式:

对于情况一,由于 $S$ 到 $lca$ 必定是一条向上的路径且 $i$ 被经过,则 $i$ 必定为 $S$ 的祖先节点,$i$ 到 $S$ 的距离必定为 $deep[S]-deep[i]$ ,加上 $w[i]$ 的观察时间,那么就是:$deep[S]-deep[i]=w[i] $ ,由此移项可得等式一:

对于情况二,由于 $lca$ 到 $T$ 必定是一条向下的路径且 $i$ 被经过,则 $lca$ 必定为 $i$ 的祖先节点,$i$ 到 $S$ 的距离必定为 $S$ 到 $lca$ 的距离加上 $i$ 到 $lca$ 的距离。那么 $i$ 到 $S$ 的距离式则为:$deep[i]-deep[lca]+deep[S]-deep[lca]$ ,加上 $w[i]$ 的观察时间等于距离,移项可得等式二:

通过这两个等式,我们分开了节点 $i$ 与路径本身,那么询问对 $i$ 并没有本质的变量影响,接着我们只需要统计即可:

首先把每个询问从 $lca$ 处断开,分为 $S-lca$ 与 $lca-T$ 两种路径。

接着我们开始按 $dfs$ 的顺序统计,由于一条路径贡献的点数有限,那么我们考虑如何计算贡献。对于两种路径,当我们向下走到某一个节点,它是某些路径处于下面的那个端点的时候,我们加上它们的贡献,而当我们离开某个节点,先统计当前节点答案,接着如果它是某些路径处于上面那个端点,我们减去它的贡献。

那么如何加减贡献与计算贡献呢?还记得之前的两个等式吗?对于一个点的统计答案,我们只需要寻找下标为 $deep[i]-w[i]$ 与下标为 $deep[i]+w[i]$ 的桶为它做出的贡献嘛。那么加减路径贡献就更简单了,如果到达路径的下方端,如果是第一种路径,那么把桶中下标为 $deep[S]$ 的位置 $++$ ,如果是第二种,那么把桶中下标为 $2*deep[lca]-deep[S]$ 的位置 $++$ ,离开路径的上方端时将对应位置 $—$ 即可。

但是很显然,对于祖先里有路径下方端的点,直接统计相关桶肯定会多余计算,我们不能统计完就清空桶,这样还是会超时,那么怎么办呢?简单,我们不能清空桶,我们可以把自己减去这个多余的贡献嘛。对于一个点,我们到达它的时候记录当前对应的桶内值,当遍历完子节点回到这个点的时候将现在的贡献见之前的贡献即可。

注意:若一条路径对 $LCA$ 有贡献,那么先在 $LCA$ 上减去这个贡献,因为拆成两条路径后会重复计算。

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,S,T,w[300001],head[300001],nx[600001],to[600001];
int size[300001],deep[300001],son[300001],fa[300001],top[300001],cir=100000;//cir做为桶下标的偏移程度,以防 2*deep[lca]-deep[S] 是个负数
int tag1[1000001],tag2[1000001],Ans[300001];//第一种、第二种路径的桶
int hd1[300001],hd2[300001],nx1[600001],nx2[600001],to1[600001],to2[600001];//询问路径挂载
int cnt,sum1,sum2;
struct Pro
{
    int t1,t2;
}k[600001];//询问拆成的两条路径对应桶的下标,如果是第一种那么t2=0,反之t1=0
void read(int &x)
{
    x=0;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
}
void add(int u,int v,int d)
{
    to[d]=v,nx[d]=head[u];
    head[u]=d;
}
void build1(int x)
{
    size[x]=1;
    top[x]=x;
    for(int i=head[x];i;i=nx[i])
        if(to[i]!=fa[x])
        {
            fa[to[i]]=x;
            deep[to[i]]=deep[x]+1;
            build1(to[i]);
            size[x]+=size[to[i]];
            if(size[to[i]]>size[son[x]])
                son[x]=to[i];
        }
}
void build2(int x)
{
    if(son[x])
    {
        top[son[x]]=top[x];
        build2(son[x]);
    }
    for(int i=head[x];i;i=nx[i])
        if(to[i]!=fa[x]&&to[i]!=son[x])
            build2(to[i]);
}//重链划分
int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(deep[top[u]]<deep[top[v]])
            swap(u,v);
        u=fa[top[u]];
    }
    if(deep[u]>deep[v])swap(u,v);
    return u;
}//树链LCA
void Ad(int t1,int t2,int d){k[d].t1=t1,k[d].t2=t2;}//添加询问
void Ad1(int u,int d){sum1++;to1[sum1]=d,nx1[sum1]=hd1[u],hd1[u]=sum1;}
void Ad2(int u,int d){sum2++;to2[sum2]=d,nx2[sum2]=hd2[u],hd2[u]=sum2;}//将询问挂载到节点上,第一个为询问加上贡献的位置的挂载,第二个为询问减去贡献的位置的挂载。
void Count(int x)
{
    int pos1=deep[x]+w[x]+cir,pos2=deep[x]-w[x]+cir;
    int now1=tag1[pos1],now2=tag2[pos2];
    for(int i=hd1[x];i;i=nx1[i])
    {
        tag1[k[to1[i]].t1]++;
        tag2[k[to1[i]].t2]++;
    }
    for(int i=head[x];i;i=nx[i])
        if(to[i]!=fa[x])
            Count(to[i]);
    Ans[x]+=tag1[pos1]-now1+tag2[pos2]-now2;
    for(int i=hd2[x];i;i=nx2[i])
    {
        tag1[k[to2[i]].t1]--;
        tag2[k[to2[i]].t2]--;
    }
}//最后统计答案
int main()
{
    read(n),read(m);
    int u,v;
    for(int i=1;i<n;i++)
    {
        read(u),read(v);
        add(u,v,i);
        add(v,u,i+n);
    }
    for(int i=1;i<=n;i++)read(w[i]);
    deep[1]=1;
    build1(1);
    build2(1);
    while(m--)
    {
        read(S),read(T);
        int lca=LCA(S,T);
        Ad(deep[S]+cir,0,++cnt);
        Ad1(S,cnt);
        Ad2(lca,cnt);
        Ad(0,deep[lca]*2-deep[S]+cir,++cnt);
        Ad1(T,cnt);
        Ad2(lca,cnt);
        if(deep[lca]+w[lca]==deep[S])Ans[lca]--;//减去重复贡献
    }//拆分、添加、挂载询问
    Count(1);
    for(int i=1;i<=n;i++)
        printf("%d ",Ans[i]);
}