可怕的天天爱跑步
AuSquare
2018-10-27 00:20:05
# 经典重温——NOIP2016最毒瘤的题目天天爱跑步
[题目链接戳这里](https://www.luogu.org/problemnew/show/P1600)
~~当年第一次考提高组本来这题想骗分结果成功的把空间开爆了可见我还是太菜了~~
## 总体思路:树上操作(求$LCA$)+桶(差分思想统计答案)
## 具体思路如下:
对于某条树上路径$u \to v$,我们可以考虑将其拆成两段,即由下至上的路径$u\to lca_{u,v}$和由上至下的路径$lca_{u,v}\to v$,对于树上的某个观察点$i$,记其观察时间为$w_i$
#### 我们首先考虑由下至上的路径$u\to lca_{u.v}$:
若该条路径的玩家能被观察员$i$观察到,即对$i$点产生贡献,则其等价条件为:
* 起点$u$在以$i$节点为根节点的子树中
* $lca_{u,v}$不在以$i$节点为根节点的子树中
* $depth_{u}=depth_i+w_i$
我们借用桶的思想,用$bucket_p$记录当前满足起点深度$depth_u=p$的路径数量.
具体的统计方法为搜索到某一节点时记录当前满足$p=depth_i+w_i$的路径条数,随后依次深度优先搜索该节点所有的子节点.回溯时删去$bucket$中记录的以该节点为$lca$的路径并将以该节点为起始节点的路径压入桶中,由于此时已经处理所有可能对该观察点产生贡献的路径,因此当前$bucket[depth_i+w_i]$的增量即为对最终答案的贡献.
附上具体片段代码
```cpp
inline void dfs1(int x) {
int bef=bucket1[w[x]+dep[x]];
for (int i=last[x];i;i=e[i].next) {if (e[i].go==fa[x][0]) continue; dfs1(e[i].go);}
for (int i=0;i<(int)opt1[x].size();i++) bucket1[opt1[x][i].t+dep[x]]+=opt1[x][i].d;
int aft=bucket1[w[x]+dep[x]];
ans[x]+=aft-bef;
}
for (int i=1; i<=m; i++) {
ca[i]=LCA(s[i],t[i]);
opt1[s[i]].push_back(PII(0,1));//实现将以该节点为根节点的路径压入桶中
opt1[ca[i]].push_back(PII(dep[s[i]]-dep[ca[i]],-1));//去除以该节点为lca的路径
}
dfs1(1);
```
#### 接下来考虑由上至下的路径$lca_{u,v}\to v$
同样若该条路径的玩家能被观察员$i$观察到,即对$i$点产生贡献,则其等价条件为:
* 路径终点$v$在以$i$节点为根节点的子树中
* $lca_{u,v}$不在以$i$节点为根节点的子树中
* $w_i-depth_i=dist(u \to v)-depth_v$~~这个式子一点也没有看起来那么显然所以最好自己画个图试一下~~
在这里我们用$bucket[p]$表示满足$p=dist(u,v)-depth_v$的路径数目
统计思路和之前相近,搜索到某一节点时记录当前的$bucket[w_i-depth_i]$,依次遍历其所有的子节点并在回溯时将以该节点为终点的路径压入桶中相应的$dist_{u,v}-depth_v$处,删除所有以该节点为$lca$的路径,最后$bucket[w_i-depth_i]$的增量即为对最终答案的贡献.
但实际上这样还是有问题的,在两次统计中我们都删除了路径可能的对其$lca$观察点的贡献,因此在对预处理数组$opt$进行操作时我们考虑将删除标记置于$lca$节点的父节点处
再次附上具体片段代码
```cpp
inline void dfs2(int x) {
int bef=bucket2[w[x]-dep[x]+N];
for (int i=0;i<(int)opt2[x].size();i++) bucket2[opt2[x][i].t-dep[x]+N]+=opt2[x][i].d;
for (int i=last[x];i;i=e[i].next) {if (e[i].go==fa[x][0]) continue; dfs2(e[i].go);}
int aft=bucket2[w[x]-dep[x]+N];
ans[x]+=aft-bef;
}
for (int i=1; i<=m; i++) {
opt2[t[i]].push_back(PII(dep[s[i]]+dep[t[i]]-2*dep[ca[i]],1));
if (fa[ca[i]][0]) opt2[fa[ca[i]][0]].push_back(PII(dep[s[i]]-dep[ca[i]]-1,-1));
/*巨佬的程序这句话看了我很久
在这里推导一下压入opt[fa[ca[i]][0].t的值
对该条路径(u,v),在该条路径lca的父节点删除该条路径影响时,
由于在搜索时的不区分写法,在这里我们实际上要使得opt[fa[ca[i]][0].t-dep[fa[ca[i]]=dist(u,v)-dep[v]
把dep[fa[ca[i]]换作dep[ca[i]]+1,得opt[fa[ca[i]][0].t=dist(u,v)dep[v]+dep[ca[i]]-1
等效于程序中的dep[u]-dep[ca[i]]-1*/
}
dfs2(1);
```
结束了吗?其实并没有.
在这种情况下还要注意一点,即$bucket$数组下标可能出现负数,则我们需要将数组下标整体平移$maxn$即可
#### 最后附上蒟蒻自己的丑陋代码
~~(其实感觉巨佬写复杂了不过一个蒟蒻又有什么资格评价呢)~~
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=301000;
struct EDGE{int to, nxt;}edge[2*maxn];
struct OPT{
int d, tmp;
OPT(){}
//OPT(){} means an empty constructor. It does not need any argument, and does nothing.
OPT(const int &_d,const int &_tmp):d(_d),tmp(_tmp){}
//OPT(){_d, _tmp):d(_d),tmp(_tmp){}. It receives two arguments and it gives the value of _d to the member d, and _tmp to tmp
};
int n, m, head[maxn], low[maxn], f[maxn][25], depth[maxn], ans[maxn], ancestor[maxn], cnt=0, w[maxn], s[maxn], t[maxn];
int bucket1[maxn], bucket2[maxn<<1];
vector <OPT> opt1[maxn], opt2[maxn];
void pre_dfs(int now) {
for (int i=head[now]; i; i=edge[i].nxt)
if (edge[i].to!=f[now][0]) {
depth[edge[i].to]=depth[now]+1; f[edge[i].to][0]=now;
for (int j=1; j<=low[depth[edge[i].to]]; j++) f[edge[i].to][j]=f[f[edge[i].to][j-1]][j-1];
pre_dfs(edge[i].to);
}
}
void addedge(int a, int b) {edge[++cnt].nxt=head[a]; edge[cnt].to=b; head[a]=cnt;}
void init() {
scanf("%d%d", &n, &m);
for (int i=1, a, b; i<n; i++) {scanf("%d%d", &a, &b); addedge(a, b); addedge(b, a);}
for (int i=1; i<=n; i++) scanf("%d", &w[i]);
for (int i=1; i<=m; i++) scanf("%d%d", &s[i], &t[i]);
low[1]=0; for (int i=2; i<=n; i++) low[i]=low[i/2]+1;
depth[1]=0; f[1][0]=0; pre_dfs(1);
}
int LCA(int a, int b) {
if (depth[a]<depth[b]) swap(a, b);
while (depth[a]>depth[b]) a=f[a][low[depth[a]-depth[b]]];
if (a==b) return b;
for (int i=low[depth[a]]; i>=0; i--)
if (f[a][i]!=f[b][i]) a=f[a][i], b=f[b][i];
return f[a][0];
}
void dfs1(int now) {
int former=bucket1[depth[now]+w[now]];
for (int i=head[now]; i; i=edge[i].nxt) if (edge[i].to!=f[now][0]) dfs1(edge[i].to);
for (int i=0; i<(int)opt1[now].size(); i++) bucket1[opt1[now][i].d]+=opt1[now][i].tmp;
int latter=bucket1[depth[now]+w[now]];
ans[now]+=latter-former;
}
void work_up() {
for (int i=1; i<=m; i++) {
ancestor[i]=LCA(s[i], t[i]);
opt1[s[i]].push_back(OPT(depth[s[i]], 1));
opt1[ancestor[i]].push_back(OPT(depth[s[i]], -1));
}
dfs1(1);
}
void dfs2(int now) {
int former=bucket2[w[now]-depth[now]+maxn];
for (int i=head[now]; i; i=edge[i].nxt) if (edge[i].to!=f[now][0]) dfs2(edge[i].to);
for (int i=0; i<(int)opt2[now].size(); i++) bucket2[opt2[now][i].d+maxn]+=opt2[now][i].tmp;
int latter=bucket2[w[now]-depth[now]+maxn];
ans[now]+=latter-former;
}
void work_down() {
for (int i=1; i<=m; i++) {
int dist=depth[s[i]]+depth[t[i]]-2*depth[ancestor[i]];
opt2[t[i]].push_back(OPT((dist-depth[t[i]]), 1));
if (f[ancestor[i]][0]) opt2[f[ancestor[i]][0]].push_back(OPT((dist-depth[t[i]]), -1));
}
dfs2(1);
}
int main() {
init();
work_up();
work_down();
for (int i=1; i<n; i++) printf("%d ", ans[i]);
printf("%d\n", ans[n]);
return 0;
}
```