#P1600. [NOIP2016 提高组] 天天爱跑步

    ID: 644 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2016线段树NOIp 提高组最近公共祖先LCA树链剖分树剖Link-Cut TreeLCT差分

[NOIP2016 提高组] 天天爱跑步

题目背景

NOIP2016 提高组 D1T2

题目描述

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

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

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

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

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

输入格式

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

接下来 n1n-1 行每行两个整数 uuvv,表示结点 uu 到结点 vv 有一条边。

接下来一行 nn 个整数,其中第 jj 个整数为 wjw_j , 表示结点 jj 出现观察员的时间。

接下来 mm 行,每行两个整数 sis_i,和 tit_i,表示一个玩家的起点和终点。

对于所有的数据,保证 1si,tin,0wjn1\leq s_i,t_i\leq n, 0\leq w_j\leq n

输出格式

输出 11nn 个整数,第 jj 个整数表示结点 jj 的观察员可以观察到多少人。

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

提示

样例 1 说明

对于 11 号点,wi=0w_i=0,故只有起点为 11 号点的玩家才会被观察到,所以玩家 11 和玩家 22 被观察到,共有 22 人被观察到。

对于 22 号点,没有玩家在第 22 秒时在此结点,共 00 人被观察到。

对于 33 号点,没有玩家在第 55 秒时在此结点,共 00 人被观察到。

对于 44 号点,玩家 11 被观察到,共 11 人被观察到。

对于 55 号点,玩家 11 被观察到,共 11 人被观察到。

对于 66 号点,玩家 33 被观察到,共 11 人被观察到。

子任务

每个测试点的数据规模及特点如下表所示。

提示:数据范围的个位上的数字可以帮助判断是哪一种数据类型。

测试点编号 n=n= m=m= 约定
121\sim 2 991991 所有人的起点等于自己的终点,即 i, si=ti\forall i,\ s_i=t_i
343\sim 4 992992 所有 wj=0w_j=0
55 993993
686\sim 8 9999499994 i[1,n1]\forall i\in[1,n-1]iii+1i+1 有边。即树退化成 1,2,,n1,2,\dots,n 按顺序连接的链
9129\sim 12 9999599995 所有 si=1s_i=1
131613\sim 16 9999699996 所有 ti=1t_i=1
171917\sim 19 9999799997
2020 299998299998

提示

(提示:由于原提示年代久远,不一定能完全反映现在的情况,现在已经对该提示做出了一定的修改,提示的原文可以在该剪贴板查看)

在最终评测时,调用栈占用的空间大小不会有单独的限制,但在我们的工作环境中默认会有 1MiB1 \text{MiB} 的限制。 这可能会引起函数调用层数较多时,程序发生栈溢出崩溃,程序中较深层数的递归往往会导致这个问题。如果你的程序需要用到较大的栈空间,请务必注意该问题。

我们可以使用一些方法修改调用栈的大小限制。

  • Linux

我们可以在终端中输入下列命令:ulimit -s 1048576。此命令的意义是,将调用栈的大小限制修改为 1048576KiB=1GiB1048576\text{KiB}=1 \text{GiB}

例如,对于如下程序 sample.cpp

#include <bits/stdc++.h>
using namespace std;
int f[1000005];
void dfs(int a){
	if(a == 0){
		f[a] = 0;
		return;
	}
	dfs(a - 1);
	f[a] = f[a - 1] + 1;
}
int main(){
	dfs(1000000);
	return 0;
}

将上述源代码用命令 g++ sample.cpp -o sample 编译为可执行文件 sample 后,使用 ./sample 执行程序。

如果在没有使用命令 ulimit -s 1048576 的情况下运行该程序,sample 会因为栈溢出而崩溃;如果使用了上述命令后运行该程序,该程序则不会崩溃。

特别地,当你打开多个终端时,它们并不会共享该命令,你需要分别对它们运行该命令。

请注意,调用栈占用的空间会计入总空间占用中,和程序其他部分占用的内存共同受到内存限制。

  • Windows

如果你使用 Windows 下的 Dev-C++,请选择 工具-编译选项 并在如下区域填入以下命令 -Wl,--stack=1073741824,填入后注意确认“编译时加入以下命令的”的框是已勾选状态。

此处 1073741824 的单位是 B/Bytes\text{B/Bytes}