超级无敌毒瘤好题——天天爱跑步
题目描述
小同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。
这个游戏的地图可以看作一棵包含个结点和条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从到的连续正整数。
现在有个玩家,第个玩家的起点为,终点为。每天打卡任务开始时,所有玩家在第秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)
小想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点的观察员会选择在第秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第秒也理到达了结点。小想知道每个观察员会观察到多少人?
注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点作为终点的玩家:若他在第秒前到达终点,则在结点的观察员不能观察到该玩家;若他正好在第秒到达终点,则在结点的观察员可以观察到这个玩家。
输入格式
第一行有两个整数和。其中代表树的结点数量,同时也是观察员的数量,代表玩家的数量。
接下来行每行两个整数和,表示结点到结点有一条边。
接下来一行个整数,其中第个整数为,表示结点出现观察员的时间。
接下来行,每行两个整数,和,表示一个玩家的起点和终点。
对于所有的数据,保证
输出格式
输出行个整数,第个整数表示结点jj的观察员可以观察到多少人。
输入样例#1:
输出样例#1:
输入样例#2:
输出样例#2:
说明
【样例1说明】
对于号点,,故只有起点为号点的玩家才会被观察到,所以玩家和玩家被观察到,共有人被观察到。
对于号点,没有玩家在第秒时在此结点,共人被观察到。
对于号点,没有玩家在第秒时在此结点,共人被观察到。
对于号点,玩家被观察到,共人被观察到。
对于号点,玩家被观察到,共人被观察到。
对于号点,玩家被观察到,共人被观察到。
【子任务】
每个测试点的数据规模及特点如下表所示。
提示:数据范围的个位上的数字可以帮助判断是哪一种数据类型。
前言
不得不说这是一道毒瘤好题。。。
毒瘤在众多的细节因为本蒟蒻太弱了
好在用非常低级的知识解决了非常麻烦的一道题,很锻炼思维。
关于部分分
根据某狗姓竞赛教练的说法,联赛出题人一般都会非常好心的出一些部分分来帮助选手们简化问题,思考问题,最终将你引向正解。
本人花了一天将此题每档部分分+正解做了一遍,一把辛酸泪。。。
测试点~
非常无脑,当且仅当点有人且时对的答案才有贡献。
给一段仅供娱乐的代码
namespace code1 {
void main() {
for(int i = 1; i < n; i++) read(), read();
for(int i = 1; i <= n; i++) w[i] = read();
for(int i = 1; i <= n; i++) ans[i] = 0;
while(m--) {
int u = read(); read();
ans[u] += w[u] == 0;
}
for(int i = 1; i <= n; i++) write(ans[i]), putchar(i == n ? '\n' : ' ');
}
}
测试点~
依旧非常无脑,当且仅当点有人出发时对的答案有贡献。
再给一段仅供娱乐的代码
namespace code2 {
void main() {
for(int i = 1; i < n; i++) read(), read();
for(int i = 1; i <= n; i++) read();
for(int i = 1; i <= n; i++) ans[i] = 0;
while(m--) {
int u = read(); read();
ans[u]++;
}
for(int i = 1; i <= n; i++) write(ans[i]), putchar(i == n ? '\n' : ' ');
}
}
测试点
因为,都很小,直接模拟每个人走的过程,求直接用的即可。
本文第一段也是最后一段正经的暴力
namespace code3 {
void dfs(int u) {
dep[u] = dep[fa[u]] + 1;
for(int e = fir[u]; e; e = E[e].nxt) {
int v = E[e].to;
if(v == fa[u]) continue;
fa[v] = u;
dfs(v);
}
}
int LCA(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
while(dep[u] > dep[v]) u = fa[u];
while(u != v) u = fa[u], v = fa[v];
return u;
}
void main() {
clear_edge();
for(int i = 1; i < n; i++) {
int u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
dfs(1);
for(int i = 1; i <= n; i++) w[i] = read();
for(int i = 1; i <= n; i++) ans[i] = 0;
while(m--) {
int u = read(), v = read(), lca = LCA(u, v), tim = 0, dis = dep[u] + dep[v] - (dep[lca] << 1);
while(u != lca) {
ans[u] += w[u] == tim;
u = fa[u], tim++;
}
ans[u] += w[u] == tim;
tim = 0;
while(v != lca) {
ans[v] += w[v] == dis - tim;
v = fa[v], tim++;
}
}
for(int i = 1; i <= n; i++) write(ans[i]), putchar(i == n ? '\n' : ' ');
}
}
测试点~
树退化成一条链,这时候该怎么办呢?
这时每条路径只有两种走法:从左到右或从右到左。
考虑从左到右(从右到左类似):当且仅当有人出发时对的答案有贡献。
那就从右往左扫一遍,维护数组,其中表示当前未结束路径中起点为的路径条数,边更新边统计答案就可以了。
注意特判越界的情况。
又臭又长的代码
namespace code4 {
struct node {int s, t;} a[maxn], b[maxn];
vector<int> tag[maxn];
void main() {
for(int i = 1; i < n; i++) read(), read();
for(int i = 1; i <= n; i++) w[i] = read();
int cnt1 = 0, cnt2 = 0;
while(m--) {
int s = read(), t = read();
if(s <= t) a[++cnt1] = (node) {s, t};
else b[++cnt2] = (node) {s, t};
}
for(int i = 1; i <= n; i++) ans[i] = 0;
for(int i = 1; i <= n; i++) bac[i] = 0, tag[i].clear();
for(int i = 1; i <= cnt1; i++) bac[a[i].s]++, tag[a[i].t].push_back(a[i].s);
for(int i = 1; i <= n; i++) {
ans[i] += i > w[i] ? bac[i - w[i]] : 0;
for(int j = 0; j < tag[i].size(); j++) bac[tag[i][j]]--;
}
for(int i = 1; i <= n; i++) bac[i] = 0, tag[i].clear();
for(int i = 1; i <= cnt2; i++) bac[b[i].s]++, tag[b[i].t].push_back(b[i].s);
for(int i = n; i >= 1; i--) {
ans[i] += i + w[i] <= n ? bac[i + w[i]] : 0;
for(int j = 0; j < tag[i].size(); j++) bac[tag[i][j]]--;
}
for(int i = 1; i <= n; i++) write(ans[i]), putchar(i == n ? '\n' : ' ');
}
}
测试点~
当所有路径的出发点是,有该怎么办呢?
因为树上路径问题与根无关,因此如果我们规定以为根的话,当且仅当时对的答案有贡献(根节点深度为)。
因此对于每个节点,求以为根的子树中有多少个终点即可,用序+前缀和乱搞一下即可。
是时候展示我真正丑陋的码风了
namespace code5 {
int tid_cnt;
int siz[maxn], tid[maxn], num[maxn], s[maxn];
void dfs(int u, int fa) {
siz[u] = 1, tid[u] = ++tid_cnt, dep[u] = dep[fa] + 1;
for(int e = fir[u]; e; e = E[e].nxt) {
int v = E[e].to;
if(v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
}
}
void main() {
clear_edge();
for(int i = 1; i < n; i++) {
int u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
for(int i = 1; i <= n; i++) w[i] = read();
tid_cnt = 0;
dep[0] = -1;
dfs(1, 0);
for(int i = 1; i <= n; i++) num[i] = 0;
while(m--) {
read(); int u = read();
num[tid[u]]++;
}
s[0] = 0;
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + num[i];
for(int i = 1; i <= n; i++) write(w[i] == dep[i] ? s[tid[i] + siz[i] - 1] - s[tid[i] - 1] : 0), putchar(i < n ? ' ' : '\n');
}
}
测试点~
刚刚我们解决了起点为的情况,那终点为呢?
还是指定为根,那么当且仅当时对的答案有贡献。
当我们扫描节点时,只需要知道以为根的子树中有多少个满足。
用桶维护即可,但是我们会发现答案可能会受到其他子树中节点的影响,因此当我们刚扫描到时先记下,当递归访问完的子树后再用此时的所得到的差值即为我们所需要的答案了。
关于我的码风,没有最丑,只有更丑
namespace code6 {
int num[maxn], bac[maxn];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
int pre = bac[dep[u] + w[u]];
bac[dep[u]] += num[u];
for(int e = fir[u]; e; e = E[e].nxt) {
int v = E[e].to;
if(v == fa) continue;
dfs(v, u);
}
ans[u] += bac[dep[u] + w[u]] - pre;
}
void main() {
clear_edge();
for(int i = 1; i < n; i++) {
int u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
for(int i = 1; i <= n; i++) w[i] = read();
for(int i = 1; i <= n; i++) num[i] = 0;
for(int i = 1; i <= m; i++) {
int u = read(); read();
num[u]++;
}
for(int i = 1; i <= n; i++) ans[i] = 0;
for(int i = 1; i <= n + n; i++) bac[i] = 0;
dep[0] = -1;
dfs(1, 0);
for(int i = 1; i <= n; i++) write(ans[i]), putchar(i == n ? '\n' : ' ');
}
}
测试点~
当当当当!!!正解要出现了!!!其实就是综上所述(逃
某王说的还是很有道理的,部分分果然是个好东西。
考虑正解时,我们先把每条路径拆分成两部分
- 的上升路径
- 的下降路径
当节点处于第一类路径时,当且仅当满足下面个条件时对的答案有贡献:
- 在的子树中,是或的祖先
用桶维护即可
小细节:当我们扫描完一个节点时,我们需要消除所有以为的路径对桶的影响(下文也会提到)
当节点处于第二类路径时,当且仅当满足下面个条件时对的答案有贡献:
- 不在的子树中,在的子树中
对上式进行转化:
因此对于节点,我们只需要统计满足上述两个条件的路径条数即可,用桶维护等式左边
来看一组样例(圆内是节点编号,圆外是的值)
两条路径分别为和
当我们统计号节点的答案时,如果不消除的影响,就会得出错误答案,为此,我们在扫描完一个节点时,需要消除所有以为的路径对桶的影响
贴上代码
namespace code7 {
int num[maxn], f[maxn][20];
vector<int> tag[maxn], era_up[maxn], era_down[maxn];
struct query {int s, t, lca;} que[maxn];
void init(int u, int fa) {
dep[u] = dep[fa] + 1;
for(int i = 1; i <= 18; i++) f[u][i] = f[f[u][i - 1]][i - 1];
for(int e = fir[u]; e; e = E[e].nxt) {
int v = E[e].to;
if(v == fa) continue;
f[v][0] = u;
init(v, u);
}
}
int LCA(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = 18; i >= 0; i--)
if(dep[f[u][i]] >= dep[v]) u = f[u][i];
if(u == v) return u;
for(int i = 18; i >= 0; i--)
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
int dis(int u, int v) {return dep[u] + dep[v] - (dep[LCA(u, v)] << 1);}
void calc_up(int u) {
int pre = bac[w[u] + dep[u]];
bac[dep[u]] += num[u];
for(int e = fir[u]; e; e = E[e].nxt) {
int v = E[e].to;
if(v == f[u][0]) continue;
calc_up(v);
}
ans[u] += bac[w[u] + dep[u]] - pre;
for(int i = 0; i < era_up[u].size(); i++) bac[era_up[u][i]]--;
}
void calc_down(int u) {
int pre = bac[w[u] - dep[u] + n];
for(int i = 0; i < tag[u].size(); i++) bac[tag[u][i] + n]++;
for(int e = fir[u]; e; e = E[e].nxt) {
int v = E[e].to;
if(v == f[u][0]) continue;
calc_down(v);
}
ans[u] += bac[w[u] - dep[u] + n] - pre;
for(int i = 0; i < era_down[u].size(); i++) bac[era_down[u][i] + n]--;
}
void main() {
clear_edge();
for(int i = 1; i < n; i++) {
int u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
dep[0] = -1;
init(1, 0);
for(int i = 1; i <= n; i++) w[i] = read();
for(int i = 1; i <= n; i++) num[i] = 0;
for(int i = 1; i <= m; i++) {
int s = read(), t = read(), lca = LCA(s, t);
num[s]++;
tag[t].push_back(dis(s, t) - dep[t]);
era_up[lca].push_back(dep[s]);
era_down[lca].push_back(dis(s, t) - dep[t]);
que[i] = (query) {s, t, lca};
}
for(int i = 1; i <= n; i++) ans[i] = 0;
for(int i = 1; i <= n + n; i++) bac[i] = 0;
calc_up(1);
for(int i = 1; i <= n + n; i++) bac[i] = 0;
calc_down(1);
for(int i = 1; i <= m; i++) {
int s = que[i].s, t = que[i].t, lca = que[i].lca;
if(dep[s] == w[lca] + dep[lca] && dis(s, t) - dep[t] == w[lca] - dep[lca]) ans[lca]--;
}
for(int i = 1; i <= n; i++) write(ans[i]), putchar(i == n ? '\n' : ' ');
}
}