(树上差分 $+$ $LCA$) $O(Mlog_2N)$
调了两个小时,最后发现把$lca$里的$y$写成$x$了,当场去世。
安利博客 (跟秦dalao的博客主题蜜汁撞车…)
首先下几个定义:
- $dis[x]$ 为$x$到根节点的距离。由于边权都是$1$,所以$dis[x] = dep[x]$
- $LCA(x, y)$ 为 $x, y$ 的最近公共祖先
- $LCA(x, y)\ down$ 为 $x, y$ 的最近公共祖先在往$y$的放下下去一格(这里不懂可以看下面的图)
- $ans[x]$ 为这个点的答案
- 我们称玩家跑的路线为”一条路径”
对于第$i$个玩家,发现可以将从$S_i$到$T_i$的路径分成两条链:
- $S_i$ 到 $LCA(S_i, T_i)$
- $LCA(S_i, T_i)\ down$ 到 $T_i$ (这里不算$LCA$,不然会重复两次 )
不太理解的同学看这张图,设$S_i = 6, T_i = 8$。其中$ LCA(6, 8)\ down = 5$
我们从每条路线对答案的贡献来看,进行分类讨论(最后的答案就是两个之和):
1. 从起点出发,终点在第一条链上(上升链):
考虑一个玩家$i$对答案的贡献:
这条玩家的起点为$S_i$ ,终点为 $LCA(S_i, T_i)$。
考虑它对答案的贡献只存在于这条链上(因为它只走过这条链上的点):
设在这条链上存在一点$x$,且到$x$点刚好为$W_x$秒,则有:
$dis[S_i] - dis[x] = W_x$
转换一下(把能从$x$直接得到的放在一边,需要统计的放在另一边):
$dis[x] + W_x = dis[S_i]$
考虑一个点得到的答案:
也就是说,当存在一个路径$S_y, T_y$使得:
$dis[x] + W_x = dis[S_y]$的时候,就看见了一个人$ans[x]++$
那我们只要建立一个数组$d1$ , $d1[x][a]$ 表示以x为节点的答案统计中, $a$这个值出现了多少次。
那么,$ans[x] = d1[x][W_x]$
但注意了,这条线到 $LCA(S_y, T_y)$ 会拐弯,$y$这个人对 $LCA(S_i, T_i)$的上面的节点答案是没有贡献的。
我们总结一下:
对于一条线的上升部分的处理,我们需要:
对于$S_i$ 到$LCA(S_i, T_i)$ 这条链上的所有点$b$,让$d1[b][dis[S_i]]++$。
这不就是树上差分吗?
我们还发现$d1$的第一维可以滚动掉,然后用一遍$dfs$动态维护这个次数。
2. 从起点出发,终点在第二条链上(下降链):
这里,我们可以用第一条链的思路进行思考,只不过改变一下细节。
考虑一个玩家$i$对答案的贡献:
这条玩家的起点为$LCA(S_i, T_i)\ down$ ,终点为 $T_i$ 。
考虑它对答案的贡献只存在于这条链上(因为它只走过这条链上的点):
设在这条链上存在一点$x$,且到$x$点刚好为$W_x$秒,则有:
$dis[S_i] + dis[x] - 2 * dis[LCA(S_i, T_i)] = W_x$
转换一下:(把能从$x$直接得到的放在一边,需要统计的放在另一边):
$W_x - dis[x] = dis[S_i] - 2 * dis[LCA(S_i, T_i)]$
考虑一个点得到的答案:
也就是说,当存在一个条路径$S_y,$使得:
$W_x - dis[x] = dis[S_y] - 2 * dis[LCA(S_y, T_y)]$的时候,就看见了一个人$ans[x]++$
我们建立一个数组$d2$ , $d2[x][a]$ 以x为节点的答案统计中, $a$这个值出现了多少次。
那么,$ans[x] = d2[x][W_x]$
我们总结一下:
对于一条线的下降部分的处理,我们需要:
对于$LCA(S_i, T_i)\ down$ 到 $T_i$ 的这条链上的所有点$b$,让$d2[b][dis[S_i] - 2 * dis[LCA(S_i, T_i)]]++$。
同理,我们这里也可以使用树上差分。
这里需要注意的一点是:$dis[S_i] - 2 * dis[LCA(S_i, T_i)]$ 可能是负数,为了不让数组越界,我们可以加一个偏移量
3. 注意事项
这种特殊(需要二维数组,滚动数组优化后)的树上差分如下:
- 存下所有点的操作序列。
- 每次到一个点的时候,把它的所有操作执行一遍。
- 注意一个特殊的点,这里可能会统计掉其他子树(旁支),所以只需开始进入的时候存一个,回溯的时候存一个,两数相减即为答案。
代码实现(我用的是倍增求LCA):
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 300005, M = N << 1, L = 19;
int n, m, fa[N][L], dis[N];
//d1的下表值域是(0 ~ 2n)的
int d1[N << 1], d2[N << 1], ans[N], w[N];
//op1, op2 分别是 d1, d2 的操作序列
//Pair(下表的值,要加的次数)
vector<PII> op1[N], op2[N];
//链式前向星
int head[N], numE = 0;
struct Edge{
int next, to;
}e[M];
void addEdge(int from, int to){
e[++numE].next = head[from];
e[numE].to = to;
head[from] = numE;
}
//预处理dfs
void dfs_(int u, int last){
fa[u][0] = last;
for(int i = 1; fa[u][i - 1]; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = head[u]; i; i = e[i].next){
int v = e[i].to;
if(v == last) continue;
dis[v] = dis[u] + 1;
dfs_(v, u);
}
}
//倍增求LCA
int lca(int x, int y){
if(dis[x] < dis[y]) swap(x, y);
for(int i = L - 1; ~i; i--)
if(dis[x] - (1 << i) >= dis[y])
x = fa[x][i];
if(x == y) return x;
for(int i = L - 1; ~i; i--)
if(fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
//添加操作序列
void update(int s, int t){
int p = lca(s, t);
op1[s].push_back(make_pair(dis[s], 1));
op1[fa[p][0]].push_back(make_pair(dis[s], -1));
op2[t].push_back(make_pair(dis[s] - 2 * dis[p] + n, 1));
op2[p].push_back(make_pair(dis[s] - 2 * dis[p] + n, -1));
}
//最后一遍dfs求答案
void dfs(int u, int last){
//v1, v2 就是我们寻找的值
int v1 = w[u] + dis[u], v2 = w[u] - dis[u] + n;
int res1 = d1[v1], res2 = d2[v2];
for(int i = head[u]; i; i = e[i].next){
int v = e[i].to;
if(v == last) continue;
dfs(v, u);
}
//加入操作
for(int i = 0; i < op1[u].size(); i++)
d1[op1[u][i].first] += op1[u][i].second;
for(int i = 0; i < op2[u].size(); i++)
d2[op2[u][i].first] += op2[u][i].second;
ans[u] = (d1[v1] - res1) + (d2[v2] - res2);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i < n; i++){
int u, v; scanf("%d%d", &u, &v);
addEdge(u, v); addEdge(v, u);
}
for(int i = 1; i <= n; i++)
scanf("%d", w + i);
dfs_(1, 0);
for(int i = 1; i <= m; i++){
int s, t; scanf("%d%d", &s, &t);
update(s, t);
}
dfs(1, 0);
for(int i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}
鸣谢:
1. 秦dalao的讲义
2. MrWriter 画图软件
3. SM.MS 的图床
我们总结一下 下面第三行的latex反复点击有惊喜
别问我是咋知道的下表值域?
额,$d1$ 数组以及 $d2$ 数组中的 $a$ 到底指的是那个。。。
有没有可能就是个符号
哪位大佬能帮忙看看哪里有问题?(它一直输出0)
%%%写的好棒!
写的可拉了
感觉几年前的我真蠢
大佬别谦虚,进步的自己回顾过去总是有不尽如人意,不过当年的你还是能给现在的我不少启发呢
对于Si 到LCA(Si,Ti) 这条链上的所有点b,让d1[b][dis[Si]]++为什么不是d1[b][dis[Si]-dis[b]]+
Thanks!
QAQ
ans[u] = (d1[v1] - res1) + (d2[v2] - res2); 这个不是很懂,如果有更多注释就好了。~ 仰望大佬~~~
res1, res2 是尚未进入 u 这颗子树时两个桶当前的答案,将 u 子树所有点加入备选桶后,d1[v1] - res1、d2[v2] - res2 即两次的偏移量即分别两种的答案
后来发现这其实好像叫dfs序差分更好一点,当时我很菜,啥都没明白就写题解了,如果误导了见谅哈哈
有点明白了。就是只统计u的子树部分。如果之前桶里有数的,就需要减掉。然后,一共是两部分。所以就相加了。~对把。好开心看懂了。谢谢
大佬又精进了~
嗯嗯
为什么DFS能通过,好像BFS就不行?
orz!(有点小细节,第二部分的总结里应该是d2和下降部分,您复制的叭qwq)
qwq被发现了
已改正