[NOIP2016 提高组] 天天爱跑步
因为本人很菜所以尽量写得通俗一点， 讲错的地方欢迎指出
参考：https://www.cnblogs.com/dmoransky/p/11406515.html orz墨染空dalao 并自己加上了一点补充
顺便弥补了一下luogu题解图炸了所以看不懂的悲剧。 但是讲得超好！！！
题目描述
小c同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线,完成打卡任务。
这个游戏的地图可以看作一一棵包含 \(n\) 个结点和 \(n-1\) 条边的树，每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 \(1\) 到 \(n\) 的连续正整数。
现在有 \(m\) 个玩家，第 \(i\) 个玩家的起点为 \(Si\) ，终点为 \(ti\) 。每天打卡任务开始时，所有玩家在第 \(0\) 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树，所以每个人的路径是唯一的)
小c想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 \(j\) 的观察员会选择在第 \(wj\) 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 \(wj\) 秒也正好到达了结点 \(j\) 。小c想知道每个观察员会观察到多少人?
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。 即对于把结点 \(j\) 作为终点的玩家：若他在第 \(wj\) 秒前到达终点,则在结点 \(j\) 的观察员不能观察到该玩家；若他正好在第 \(wj\) 秒到达终点,则在结点 \(j\) 的观察员可以观察到这个玩家。
离线赛被虐爆了qaq。
初步分析
- 按着题目要求说， 我们需要看每个观察员会观察到几个人
- 而每个观察员可以观察到几个人和 \(w[]\) 数组有关， 也就是找满足要求的点
- 我们可以拆分一下。
- 把 \(s\) 到 \(t\) 的路径 （经过lca） 分成两段
这样算每段的贡献加起来就是答案了。
算出什么点能有贡献
如果是在一条链上， 即
明显可以发现：
对于所有如上图所示的点t， 若 \(dep[t]== dep[x]+ w[x]\) 那都可以算入贡献。 这里 \(dep\) 指深度
而 \(dep[x]+ w[x]\) 是一个固定的值， 在 \(x\) 的子树外的点一定不会对 \(x\) 产生贡献，不在这链上的或在链上但没有经过的也不会对 \(x\) 产生贡献。
所以我们要求的就是 在 \(x\) 的子树内的， 在这条链上的， 且 \(dep[t]== dep[x]+ w[x]\) 的所有点 \(t\) 的个数 这是第一种情况
写法
先来看一看怎么写（写法很巧妙）。
- 我们开一个桶， 存 \(dep\) 值
解决在子树内的问题
- 首先要满足在其子树内。 不可能每个点开一个桶存其子树的信息， 但是我们要求， 怎么办。
看下面伪伪代码（不会伪代码qaq
\(s[]\) 表示那个桶
void dfs(int u)
res= 要求的值 val= s[res]
for(all vertex that u could reach ） //就是任何u能遍历到的点， 尝试高大上一点但是失败了 这里没有考虑树的情况
dfs(j)
s[res]++
ans[u]= s[res]- val
啊不用管一些细节问题， 大概理解思路就好了。
也就是进入子树了， 记录一个以前的值， 记录一个最后的值， 减去就是多出的值了。
成功解决。
如何解决不在链上的问题
我们可以发现， 每次有一个起点 \(s\) 和终点 \(t\)， 只有那一段区间是可以加的。 （这里可能有点表述不清， 我们在上上图已经把一条链拆成了两段， 看第一段）
那好了， 我们可以用树上差分的思想， 把每一次操作放在点上， 在遍历到起点时，我们加一， 终点的时候， 我们减1
如图
另一条链的写法
差不多是一样的。 另一条链如果要产生贡献必须要 \(dep[s]+ dep[x]- dep[lca(s, t)]== w[x]\) 这个可以自己画图看一看
移项： \(dep[s]- dep[lca(s, t)]== dep[x]+ w[x]\)
然后就和上面一样了
代码
#include <bits/stdc++.h>
using namespace std;
const int N= 300005, M= N* 2;
typedef pair<int, int> PII;
int h[N], e[M], ne[M], idx;
int dep[N], fa[N][25], w[N];
int d1[N<< 1], d2[N<< 1];
int ans[N];
int n, m;
void init() //这里使用倍增求lca
{
memset(dep, 0x3f, sizeof dep);
dep[0]= 0, dep[1]= 1; queue<int> q; q.push(1);
while(q.size())
{
int u= q.front(); q.pop();
for(int i= h[u]; ~i; i= ne[i])
{
int j= e[i];
if(dep[j]> dep[u]+ 1)
{
dep[j]= dep[u]+ 1; fa[j][0]= u;
for(int k= 1; k<= 24; k++ )
fa[j][k]= fa[fa[j][k- 1]][k- 1];
q.push(j);
}
}
}
return ;
}
void add(int a, int b)
{
e[idx]= b, ne[idx]= h[a], h[a]= idx++ ;
return;
}
int lca(int a, int b)
{
if(dep[a]< dep[b]) swap(a, b);
for(int i= 24; i>= 0; i-- )
if(dep[fa[a][i]]>= dep[b]) a= fa[a][i];
if(a== b) return a;
for(int i= 24; i>= 0; i-- )
if(fa[a][i]!= fa[b][i]) a= fa[a][i], b= fa[b][i];
return fa[a][0];
}
vector<PII> query1[N], query2[N];
void update(int s, int t) //存储询问
{
int p= lca(s, t); //query1[i].first 表示此点能给出的贡献， second是1或-1
query1[s].push_back((PII){dep[s], 1}); query1[fa[p][0]].push_back({dep[s], -1}); //分成两段分开来存
query2[t].push_back((PII){dep[s]- 2* dep[p]+ n, 1}); query2[p].push_back({dep[s]- 2* dep[p]+ n, -1});
return ;
}
void dfs(int u, int fa)
{
int v1= w[u]+ dep[u], v2= w[u]- dep[u]+ n;
int res1= d1[v1], res2= d2[v2]; //和上述伪代码差不多。。？
for(int i= h[u]; ~i; i= ne[i])
{
int j= e[i];
if(j== fa) continue; //防止重复到一个点
dfs(j, u);
}
for(int i= 0; i< query1[u].size(); i++ ) d1[query1[u][i].first]+= query1[u][i].second; //树上差分的思路
for(int i= 0; i< query2[u].size(); i++ ) d2[query2[u][i].first]+= query2[u][i].second;
ans[u]= (d1[v1]- res1)+ (d2[v2]- res2); //上述讲过， 一个常见的套路， 做差
return ;
}
int main()
{
cin>> n>> m;
memset(h, -1, sizeof h);
for(int i= 1; i<= n- 1; i++ )
{
int a, b; scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
for(int i= 1; i<= n; i++ ) scanf("%d", &w[i]);
init(); //预处理出倍增数组
for(int i= 1; i<= m; i++ )
{
int s, t; scanf("%d%d", &s, &t);
update(s, t);
}
dfs(1, -1);
for(int i= 1; i<= n; i++ ) printf("%d ", ans[i]);
puts("");
return 0;
}
此题最好的地方就是代码不太长 （逃）