知识点: 树上差分，线段树合并

原题面 Loj Luogu

扯

之前口嗨的时候说自己可以用线段树合并过去然后发现自己并不会做硬刚了很长时间终于刚了出来但是思路奇特实现复杂把代码写的奇丑无比自己看见都会吐而且在写题解之前还扯这么一大堆madan上面这一堆话已经差不多到了一百字了再不停下来就会被当成傻逼的 Luckyblock 是人间之屑再最后还要提醒您一句没事不要yy奇怪的解法请务必能写正解就写正解。

有道翻译：
Mouth before hi said can use line segment tree merging himself in the past and then found myself will not do hard just for a long time finally just out but thought strange complex write code ugly he would vomit and see also pull such a pile of a junior before you write the answer key on a pile of these words has almost one hundred words he did not stop will be as a shitty Luckyblock is the chip of the human world finally will remind you again ok please don't yy strange method can write truth is truth

重新转成中文：
嗨之前的嘴巴说过可以用线段树合并过去，然后发现自己很长时间不会努力，最后才出来，但以为奇怪的复杂代码写得很丑，他会呕吐，还看到拉了这么一大堆 在您将答案键写在这些单词上之前，他有将近一百个单词，而他并没有停下来，这是一个卑鄙的Luckyblock，是人类世界的筹码，最终会再次提醒您好吗？ 是事实

题意简述

给定一棵 \(n\) 个节点的树，点有点权 \(w_i\)。
给定 \(m\) 个人的起点终点，\(0\) 时刻时他们均在自己的起点位置。
之后他们都会沿最短路径向终点移动，每个时刻移动一条边。
对于每一个节点 \(i\)，求 \(w_i\) 时刻时出现在 \(i\) 的人数。
\(1\le n,m\le 3\times 10^5\)，\(1\le s_i,t_i,w_i\le n\)。

分析题意

考虑路径 \(s_i\rightarrow t_i\)的影响：

对于 \(s_i\rightarrow \operatorname{lca}\) 上的节点 \(j\)，显然路径对它有贡献的条件为：

移项，有：

\(dep\) 与 \(w\) 均为已知量，可预处理所有节点的 \(dep +w\)。
查询路径对 \(s_i\rightarrow \operatorname{lca}\) 有贡献的结点数量，等价于查询 \(s_i\rightarrow \operatorname{lca}\) 上 \(dep_j+w_j=dep_{s_i}\) 的数量。

具体地，考虑对每一个节点都维护一棵权值线段树。
对于路径 \(s_i\rightarrow t_i\)，令 \(s_i\rightarrow \operatorname{lca}\) 所有节点的权值线段树上 \(dep_{s_i}\) 的出现次数 + 1。
显然可以树上差分 + 线段树合并维护。

对于节点 \(j\)，查询该节点权值线段树上 \(dep_j + w_j\) 的个数，即为该点答案的增量。

对于 \(\operatorname{lca}\rightarrow t_i\) 上的节点 \(j\)，同理，路径对它有贡献的条件为：

移项，有：

同理，查询路径对 \(\operatorname{lca}\rightarrow t_i\) 有贡献的结点数量，等价于查询 \(\operatorname{lca}\rightarrow t_i\) 上 \(dep_j-w_j = 2\times dep_{\operatorname{lca}}-dep_{s_i}\) 的数量。

按上述过程线段树合并维护即可。

亿些细节

上述过程中将 \(s_i\rightarrow t_i\) 拆分成 \(s_i \rightarrow \operatorname{lca}\) 和 \(\operatorname{lca}\rightarrow t_i\) 考虑，一条路径 \(\operatorname{lca}\) 的贡献统计了两次。
设 \(x\) 为 \(s_i\) 的一个祖先，满足\(dep_x= dep_{\operatorname{lca}}+1\)。
把路径拆成 \(s_i \rightarrow x\) 和 \(\operatorname{lca} \rightarrow t_i\)，即可避免重复贡献。
\(x\) 显然可简单倍增求得。

注意讨论 \(s_i = \operatorname{lca}\)，\(t_i=\operatorname{lca}\)，\(s_i=t_i\) 的情况。

注意求 \(x\) 时，如果在一开始 swap 了两个节点，返回值的时候也要再 swap 回来。

如果线段树合并是不新建节点的写法，
统计某节点贡献 要在 线段树合并到该节点时统计，不可全部合并完再统计。

权值线段树维护的值域中有负数时，注意添加偏移量。

计算完 \(s_i\rightarrow x\) 的贡献后注意清空，可懒惰删除。

代码实现

写的奇丑，没有任何参考价值。
建议自行 yy。

//知识点：树上差分，线段树合并 
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define ls (lson[now_])
#define rs (rson[now_])
const int kMaxn = 3e5 + 10;
const int kInf = 5e5 + 10;
//=============================================================
int edge_num, w[kMaxn], head[kMaxn], v[kMaxn << 1], ne[kMaxn << 1];
int n, m, delta, node_num, root[kMaxn], lson[kMaxn << 6], rson[kMaxn << 6], sum[kMaxn << 6];
int dep[kMaxn], fa[kMaxn][22];
int qu[kMaxn], qv[kMaxn], lca[kMaxn], ans[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void AddEdge(int u_, int v_) {
  v[++ edge_num] = v_; ne[edge_num] = head[u_], head[u_] = edge_num;
}
void Dfs1(int u_, int fat_) {
  fa[u_][0] = fat_;
  dep[u_] = dep[fat_] + 1;
  for (int i = 1; i < 20; ++ i) {
    fa[u_][i] = fa[fa[u_][i - 1]][i - 1];
  }
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fat_) continue ;
    Dfs1(v_, u_);
  }
}
int GetLca(int x_, int y_, bool flag_) {
  bool flag_swap = false;
  if (dep[x_] < dep[y_]) {
    std :: swap(x_, y_); 
    flag_swap = true;
  }
  for (int i = 20; i >= 0; -- i) {
    if (dep[fa[x_][i]] > dep[y_]) {
      x_ = fa[x_][i];
    }
  }
  if (fa[x_][0] == y_) return flag_ ? x_ : y_;
  if (dep[x_] > dep[y_]) x_ = fa[x_][0];
  for (int i = 20; i >= 0; -- i) {
    if (fa[x_][i] != fa[y_][i]) {
      x_ = fa[x_][i], y_ = fa[y_][i];
    }
  }
  if (flag_swap) return flag_ ? y_ : fa[y_][0];
  return flag_ ? x_ : fa[x_][0];
}
void Clear(int now_) {
  ls = rs = sum[now_] = 0;
}
void Update(int now_) {
  sum[now_] = sum[ls] + sum[rs];
}
void Insert(int &now_, int L_, int R_, int pos_, int val_) {
  if (! now_) {
    now_ = ++ node_num;
    Clear(node_num);
  }
  if (L_ == R_) {
    sum[now_] += val_;
    return ;
  }
  int mid = (L_ + R_) >> 1;
  if (pos_ <= mid) Insert(ls, L_, mid, pos_, val_);
  else Insert(rs, mid + 1, R_, pos_, val_);
  Update(now_);
}
int Merge(int now_, int y_, int L_, int R_) {
  if (! now_ || ! y_) return now_ + y_;
  if (L_ == R_) {
    sum[now_] += sum[y_];
    return now_;
  }
  int mid = (L_ + R_) >> 1;
  ls = Merge(ls, lson[y_], L_, mid);
  rs = Merge(rs, rson[y_], mid + 1, R_);
  Update(now_);
  return now_;
}
int Query(int now_, int L_, int R_, int pos_) {
  if (L_ == R_ || ! sum[now_]) return sum[now_];
  int mid = (L_ + R_) >> 1;
  if (pos_ <= mid) return Query(ls, L_, mid, pos_);
  else return Query(rs, mid + 1, R_, pos_);
}
void Dfs(int u_, bool flag_) {
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa[u_][0]) continue ;
    Dfs(v_, flag_);
    root[u_] = Merge(root[u_], root[v_], 1, kInf);
  }
  if (! flag_) ans[u_] += Query(root[u_], 1, kInf, dep[u_] + w[u_]);
  if (flag_) ans[u_] += Query(root[u_], 1, kInf, dep[u_] - w[u_] + delta);
}
//=============================================================
int main() {
  delta = n = read(), m = read();
  for (int i = 1; i < n; ++ i) {
    int u = read(), v = read();
    AddEdge(u, v), AddEdge(v, u);
  }
  Dfs1(1, 0);
  for (int i = 1; i <= n; ++ i) w[i] = read();
  for (int i = 1; i <= m; ++ i) {
    qu[i] = read(), qv[i] = read(), lca[i] = GetLca(qu[i], qv[i], true);
    if (qu[i] == qv[i]) {
      Insert(root[qu[i]], 1, kInf, dep[qu[i]], 1);
      if (fa[qu[i]][0]) Insert(root[fa[qu[i]][0]], 1, kInf, dep[qu[i]], - 1);
      continue ;
    }
    if (qu[i] == fa[lca[i]][0]) continue ;
    Insert(root[qu[i]], 1, kInf, dep[qu[i]], 1);
    if (fa[lca[i]][0] == qv[i]) {
      if (fa[lca[i]][1]) Insert(root[fa[lca[i]][1]], 1, kInf, dep[qu[i]], - 1);
      continue ; 
    }
    if (fa[lca[i]][0]) Insert(root[fa[lca[i]][0]], 1, kInf, dep[qu[i]], - 1);
  }
  Dfs(1, false);
  node_num = 0;
  memset(root, 0, sizeof (root));
  for (int i = 1; i <= m; ++ i) {
    lca[i] = fa[lca[i]][0];
    if (qv[i] == lca[i] || qu[i] == qv[i]) continue ;
    Insert(root[qv[i]], 1, kInf, 2 * dep[lca[i]] - dep[qu[i]] + delta, 1);
    if (fa[lca[i]][0]) Insert(root[fa[lca[i]][0]], 1, kInf, 2 * dep[lca[i]] - dep[qu[i]] + delta, - 1);
  }
  Dfs(1, true);
  for (int i = 1; i <= n; ++ i) printf("%d ", ans[i]);
  return 0;
}