（这里展示的是NOIP2016的题面）
天天爱跑步(running)
每个测试点时限：2.0秒
内存限制：512MB
【问题描述】
小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。
这个游戏的地图可以看作一棵包含n个结点和n−1条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从1到n的连续正整数。
现在有m个玩家，第i个玩家的起点为Si，终点为Ti。每天打卡任务开始时，所有玩家在第0秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）
小C想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 jj 的观察员会选择在第Wj秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也正好到达了结点Wj。小C想知道每个观察员会观察到多少人？
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点j作为终点的玩家：若他在第
Wj秒前到达终点，则在结点j的观察员不能观察到该玩家；若他正好在第
Wj秒到达终点，则在结点j的观察员可以观察到这个玩家。
【输入格式】
从文件running.in中读入数据。
第一行有两个整数n和m。其中n代表树的结点数量，同时也是观察员的数量，m代表玩家的数量。
接下来n−1行每行两个整数u和v，表示结点u到结点v有一条边。
接下来一行n个整数，其中第j个整数为Wj，表示结点j出现观察员的时间。
接下来m行，每行两个整数Si和Ti，表示一个玩家的起点和终点。
对于所有的数据，保证1⩽，0\leqslant
W_j\leqslant n。
【输出格式】
输出到文件running.out中。
输出1行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
【子任务】
测试点编号
|
n
|
m
|
约定
|
1
|
=991
|
=991
|
所有人的起点等于自己的终点，
即S_i=T_i
|
2
|
|||
3
|
=992
|
=992
|
W_j=0
|
4
|
|||
5
|
=993
|
=993
|
无
|
6
|
=99994
|
=99994
|
树退化成一条链，其中1与2有边，2与3有边. . .，n-1与n有边
|
7
|
|||
8
|
|||
9
|
=99995
|
=99995
|
所有的S_i=1
|
10
|
|||
11
|
|||
12
|
|||
13
|
=99996
|
=99996
|
所有的T_i=1
|
14
|
|||
15
|
|||
16
|
|||
17
|
=99997
|
=99997
|
无
|
18
|
|||
19
|
|||
20
|
=299998
|
=299998
|
【解析】
此题难度较大，细节较多。
对于测试点1~5，直接模拟即可。
对于剩下的测试点，强行模拟每个玩家的行为显然不可取的。由于每个节点的W_i值是固定的，可能被该节点观察到的玩家的起点与该节点的距离一定为W_i。
于是，对于测试点6~8，节点i的观察员可能观察到的玩家的起点一定是i-W_i或i+W_i。将玩家分为向左走和向右走两类（不移动的玩家可以视为向右走），用int数组cnt[i]表示起点为i且终点未被处理的玩家的个数，用vector<int>数组start[i]和end[i]表示全体以节点i为起点或终点的玩家编号。首先从左向右扫描节点，只处理向右走的玩家（start[]、end[]只包含向右的玩家），对于当前节点i，令cnt[i]+=start[i].size()，ans[i]+=cnt[i-W_i]，这样便得到了节点i的观察员可以观察到的所有从左边过来的玩家，为了避免重复，接下来需要遍历end[i]数组，减去已经到达终点的玩家。用类似的方式从右向左再扫描一遍即可得到答案。复杂度 \Theta(n)。核心代码如下：
//预处理start和end
for (int i = 1; i <= m;
i++)
{
//玩家向右走
if
(player[i].second >= player[i].first)
{
start[player[i].first].push_back(i);
end[player[i].second].push_back(i);
}
}
//从左往右扫描
for (int i = 1; i <= n;
i++)
{
cnt[i] +=
start[i].size();
ans[i] += cnt[i
- w[i] < 0 ? 0 : i - w[i]];
for (auto j: end[i]) cnt[player[j].first]--;
}
对于测试点9~12，只有满足h_i=W_i+1（h_i表示节点i的高度，根节点高度为1）的观察员才可能观察到玩家。在满足该条件的前提下，一个玩家可以被位于节点i的观察者观察到，当且仅当该玩家的终点在节点i的子树上。我们可以用树形dp解决。
对于测试点13~16，设s为某个玩家的起点，a为某个可以观察到该玩家的观察员所在节点，有h_s-h_a=W_a。移向，h_s=W_a+h_a。对于任何一个观察员，W_a+h_a是定值。如果用数组cnt[i]表示起点的高度为i的玩家的个数，假设已经处理的所有玩家的起点都是i的子节点，ans[i]=cnt[i]。如果我们按dfs的逆序处理玩家和观察员就可以保证这个假设。但由于一个节点有多个子节点，我们无法像测试点6~8那样为不同阶段找到一个全序。对于每个节点，我们都维护一个cnt数组，如果将数组的加法运算定义为将数组的不同元素顺次相加（c=a+b\Leftrightarrow c_i=a_i+b_i），一个节点i的cnt数组等于i的子节点的cnt数组的和。如果用动态开点的权值线段树存储cnt数组，我们可以用线段树合并解决这一问题。核心代码：
//预处理
void init()
{
height[1] = 1;
dfs1(1);//获取每个节点的高度
for (int i = 1; i <=
n; i++)
{
build(tree1[i]);//为每个节点建立一棵权值线段树
}
for (int i = 1; i <=
m; i++)
{
//将玩家起点的高度信息存放在玩家的起点的权值线段树中
updata(height[player[i].s], 1, -n, n,
tree1[player[i].s]);
}
}
//获得答案
void dfs2(int now)
{
vis[now] = 2;
for (vector<int>::iterator i = graph[now].begin();i!=graph[now].end(); i++)
{
if (vis[*i] != 2)
{
dfs2(*i);
//线段树合并
tree1[now] = merge(tree1[now], tree1[*i]);
}
}
//查询cnt[w[now]+height[now]]的值
ans[now] = query(w[now] + height[now], -n, n, tree1[now]);
}
线段树合并的代码如下：
tree_t* merge(tree_t *t1, tree_t *t2)
{
if (t1 == NULL)return t2;
if (t2 == NULL)return t1;
t1->sum += t2->sum;
t1->left = merge(t1->left, t2->left);
t1->right = merge(t1->right, t2->right);
return t1;
}
对于测试点17~20，参考测试点13~16的思路，设s、a、p、t为树上的三个节点，其中p=LCA(s,t)，s为玩家的起点，t为玩家的终点，a为某个可以观察的该玩家的节点。路径 s\rightarrow t可以被分成两段： s\rightarrow p、 p\rightarrow t。情况一：a位于路径 s\rightarrow p上，h_s=W_a+h_a；情况二：a位于路径 p\rightarrow t上，设time为点s到点t的距离，有time-(h_t-d_a)=W_a，移向得time-h_t=W_a-h_a，等式左边之和玩家有关，等式右边只和观察员有关。对于每个节点，我们用两棵权值线段树tree1、tree2分别维护h_s和time-h_t，更新时同样使用线段树合并。
刚才的分析似乎遗漏了一些情况：假如a和p是同一个点，究竟应该属于情况一还是情况二呢？显然这种情况被重复考虑了，统计答案时需要减去。下文中，称这种情况为情况三。处理完情况三后的核心代码如下：
void dfs2(int now)
{
vis[now] = 2;
for (auto i:graph[now])
{
if (vis[i] != 2)
{
dfs2(i);
tree1[now] = merge(tree1[now], tree1[i]);
tree2[now] = merge(tree2[now], tree2[i]);
}
}
//用tmp1存储查询结果仅仅是方便调试
int tmp1 = query(w[now] + height[now], -n, n, tree1[now]);
int tmp2 = query(w[now] - height[now], -n, n, tree2[now]);
ans[now] = tmp1 + tmp2
- lcacnt[now];
}
void init()
{
height[1] = 1;
dfs1(1);
//树上倍增求LCA的预处理
for (int j = 1; j <=
18; j++)
{
for (int i = 1; i <=
n; i++)
{
parent[i][j]
= parent[parent[i][j - 1]][j - 1];
}
}
for (int i = 1; i <=
n; i++)
{
build(tree1[i]);
build(tree2[i]);
}
for (int i = 1; i <=
m; i++)
{
int plca = lca(player[i].s, player[i].t);
player[i].time
= height[player[i].s] + height[player[i].t] - 2 * height[plca];
//观察者恰好在LCA的情况
if (height[plca] -
height[player[i].s] == w[plca]||
player[i].time
- height[player[i].t] + height[plca] == w[plca]) lcacnt[plca]++;
updata(height[player[i].s], 1, -n, n,
tree1[player[i].s]);
updata(player[i].time -
height[player[i].t], 1, -n, n, tree2[player[i].t]);
}
}
即使这样，我们仍然遗漏了情况。如果一个玩家的路径完全位于i的子树内，他理应不可能被节点i观察到，可根据情况一、二得到的等式可能会统计到这种情况的玩家。为了解决这个问题，我们维护两个vector<int>数组tree1_、tree2_，tree1_[i]表示所有LCA为i的玩家的h_s值，类似地，tree2_[i]表示所有LCA为i的玩家的time-h_t的值。这两个数组维护的信息与tree1、tree2是对应的，只是维护的方式和位置不同。在init()函数中添加对tree1_和tree2_的预处理，在dfs2()函数中遍历tree1_[now]和tree2_[now]即可。如此处理之后，情况三从原本的被重复考虑变成了现在的被遗漏。细节见代码：
void dfs2(int now)
{
vis[now] = 2;
for (auto i:graph[now])
{
if (vis[i] != 2)
{
dfs2(i);
tree1[now] = merge(tree1[now], tree1[i]);
tree2[now] = merge(tree2[now], tree2[i]);
}
}
//除去起点和终点都在子树内的情况
for (auto i:tree1_[now])
{
updata(i, -1, -n, n, tree1[now]);
}
for (auto i:tree2_[now])
{
updata(i, -1, -n, n, tree2[now]);
}
int tmp1 = query(w[now] + height[now], -n, n, tree1[now]);
int tmp2 = query(w[now] - height[now], -n, n, tree2[now]);
//减号变成了加号
ans[now] = tmp1 + tmp2
+ lcacnt[now];
}
void init()
{
height[1] = 1;
dfs1(1);
for (int j = 1; j <=
18; j++)
{
for (int i = 1; i <=
n; i++)
{
parent[i][j]
= parent[parent[i][j - 1]][j - 1];
}
}
for (int i = 1; i <=
n; i++)
{
build(tree1[i]);
build(tree2[i]);
}
for (int i = 1; i <=
m; i++)
{
int plca =
lca(player[i].s, player[i].t);
player[i].time
= height[player[i].s] + height[player[i].t] - 2 * height[plca];
if (height[plca] -
height[player[i].s] == w[plca] ||
player[i].time
- height[player[i].t] + height[plca] == w[plca]) lcacnt[plca]++;
updata(height[player[i].s], 1, -n, n,
tree1[player[i].s]);
updata(player[i].time -
height[player[i].t], 1, -n, n, tree2[player[i].t]);
//有变化的部分
tree1_[plca].push_back(height[player[i].s]);
tree2_[plca].push_back(player[i].time -
height[player[i].t]);
}
}
此外这道题还卡常数，动态开点时不能左右节点同时开；不要用new分配空间。
【参考程序】
//w[a]+height[a]==height[s]
//w[a]-height[a]==time[s->t]-height[t]
//lca处
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
namespace Solution{
template<typename tp>
void read(tp &x)
{
char ch = getchar(); x = 0; bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
int n, m;
//线段树的节点，为了节约空间，没有存放区间的左右端点l、r
struct tree_t
{
tree_t *left, *right;
int sum;
};
vector <int>
graph[300001];
tree_t *tree1[300001];//height[s],在起点维护
tree_t *tree2[300001];//time[s->t]-height[t]，在终点维护
int height[300001];
char vis[300001];//vis用时间戳判重，节约memset时间
int parent[300001][19];
int ans[300001];
int w[300001];
int lcacnt[300001];//在w[i]时刻经过lca节点的路径的个数
vector <int>
tree1_[300001];//height[s],在LCA处维护
vector <int>
tree2_[300001];//time[s->t]-height[t]，在LCA处维护
int tail = 0;
tree_t RAM[15000000];
//手写new，卡常数
tree_t *new2()
{
return RAM + tail++;
}
struct player_t
{
int s, t;
int time;
}player[300001];
//建树（其实这个函数没什么功能）
void build(tree_t *&root)
{
if (root)return;
root = new2();
}
//单点加，p：修改的位置，x:加的值
void updata(int p, int x, int nowl, int nowr, tree_t *now)
{
if (now == NULL)return;
if (nowl == nowr)
{
now->sum += x;
return;
}
int mid = nowl + nowr >> 1;
if (p <= mid)
{
if (now->left == NULL)
{
now->left =
new2();
}
updata(p, x, nowl, mid, now->left);
}
else
{
if (now->right == NULL)
{
now->right =
new2();
}
updata(p, x, mid + 1, nowr, now->right);
}
//等价于now->sum=now->left->sum+now->right->sum但不用特判空指针
//其实不写也可以
now->sum += x;
}
//单点查询
int query(int p, int nowl, int nowr, tree_t *now)
{
if (now == NULL)return 0;
if (p>nowr || p<nowl)return 0;
if (nowl == nowr)return now->sum;
int mid = nowl + nowr >> 1;
if (p <= mid)return query(p, nowl, mid, now->left);
else return query(p, mid + 1, nowr, now->right);
}
//线段树合并，注意：合并意味着销毁原来的线段树
tree_t* merge(tree_t *t1, tree_t *t2)
{
if (t1 == NULL)return t2;
if (t2 == NULL)return t1;
t1->sum += t2->sum;
t1->left = merge(t1->left, t2->left);
t1->right = merge(t1->right, t2->right);
return t1;
}
//预处理高度和父节点
void dfs1(int now)
{
vis[now] = 1;
//C++11新特性，NOIP上会CE，这样写主要是为了增加代码可读性
for (auto i:graph[now])
{
if (!vis[i])
{
parent[i][0]
= now;
height[i]
= height[now] + 1;
dfs1(i);
}
}
}
//按dfs逆序获取答案
void dfs2(int now)
{
vis[now] = 2;
for (auto i:graph[now])
{
if (vis[i] != 2)
{
dfs2(i);
tree1[now] = merge(tree1[now], tree1[i]);
tree2[now] = merge(tree2[now], tree2[i]);
}
}
//除去起点和终点都在子树内的情况
for (auto i:tree1_[now])
{
updata(i, -1, -n, n, tree1[now]);
}
for (auto i:tree2_[now])
{
updata(i, -1, -n, n, tree2[now]);
}
int tmp1 = query(w[now] + height[now], -n, n, tree1[now]);
int tmp2 = query(w[now] - height[now], -n, n, tree2[now]);
//a位于s->p段 + a位于p->t段 + a等于p
ans[now] = tmp1 + tmp2
+ lcacnt[now];
}
//用树上倍增求LCA
int lca(int x, int y)
{
if (height[x]<height[y])swap(x, y);
for (int i = 18; i >=
0; i--)
{
if (height[parent[x][i]] >=
height[y])x = parent[x][i];
}
if (x == y)return x;
for (int i = 18; i >=
0; i--)
{
if (parent[x][i] != parent[y][i])
{
x = parent[x][i];
y = parent[y][i];
}
}
return parent[x][0];
}
void init()
{
height[1] = 1;
dfs1(1);
for (int j = 1; j <=
18; j++)
{
for (int i = 1; i <=
n; i++)
{
parent[i][j]
= parent[parent[i][j - 1]][j - 1];
}
}
for (int i = 1; i <=
n; i++)
{
build(tree1[i]);
build(tree2[i]);
}
for (int i = 1; i <=
m; i++)
{
int plca = lca(player[i].s, player[i].t);
player[i].time
= height[player[i].s] + height[player[i].t] - 2 * height[plca];
if (height[plca] -
height[player[i].s] == w[plca] ||
player[i].time
- height[player[i].t] + height[plca] == w[plca])lcacnt[plca]++;
updata(height[player[i].s], 1, -n, n,
tree1[player[i].s]);
updata(player[i].time -
height[player[i].t], 1, -n, n, tree2[player[i].t]);
tree1_[plca].push_back(height[player[i].s]);
tree2_[plca].push_back(player[i].time -
height[player[i].t]);
}
}
int main()
{
read(n); read(m);
for (int i = 1; i<n;
i++)
{
int u, v;
read(u); read(v);
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i <=
n; i++)
{
read(w[i]);
}
for (int i = 1; i <=
m; i++)
{
read(player[i].s);
read(player[i].t);
}
init();
dfs2(1);
for (int i = 1; i <=
n; i++)
{
printf("%d ", ans[i]);
}
return 0;
}
}
int main()
{
freopen("running.in", "r", stdin);
freopen("running.out", "w", stdout);
return Solution::main();
}
/*
in
4 1
1 3
2 3
3 4
2 0 0 0
2 4
out
0 1 0 0
*/