（这里展示的是NOIP2016的题面）
天天爱跑步(running)
每个测试点时限：2.0秒
内存限制：512MB
【问题描述】
小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。
这个游戏的地图可以看作一棵包含$n$个结点和$n−1$条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从$1$到$n$的连续正整数。
现在有$m$个玩家，第$i$个玩家的起点为$S_i$，终点为$T_i$。每天打卡任务开始时，所有玩家在第$0$秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）
小C想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 jj 的观察员会选择在第$W_j$秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第$W_j$秒也正好到达了结点$W_j$。小C想知道每个观察员会观察到多少人？
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点$j$作为终点的玩家：若他在第
$W_j$秒前到达终点，则在结点$j$的观察员不能观察到该玩家；若他正好在第
$W_j$秒到达终点，则在结点$j$的观察员可以观察到这个玩家。
【输入格式】
从文件running.in中读入数据。
第一行有两个整数$n$和$m$。其中$n$代表树的结点数量，同时也是观察员的数量，$m$代表玩家的数量。
接下来$n-1$行每行两个整数$u$和$v$，表示结点$u$到结点$v$有一条边。
接下来一行$n$个整数，其中第$j$个整数为$W_j$，表示结点$j$出现观察员的时间。
接下来$m$行，每行两个整数$S_i$和$T_i$，表示一个玩家的起点和终点。
对于所有的数据，保证$1\leqslant S_i,T_i\leqslant n $，$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
*/
没有评论:
发表评论