UOJ261【NOIP2016】天天爱跑步

发表于

  题意:一棵$n$个点的树，每个点$i$有权值$w_i$，$m$条路径，对每个点i求出有多少条路径经过i且路径起点与$i$的距离为$w_i$。

  最近清noip题目发现这道题还没有做。回头来看，这道题仍然给我不小的收获。
  我们将路径$(u, v)$拆成向上路径$(u, lca)$和向下路径$(lca, v)$。首先考虑向上的路径。
  一条向上的路径$(u, v)$对点i有贡献，当且仅当:
  1、u在i的子树中
  2、$dep[u] = dep[i] + w[i]$
  3、路径经过i，即不会在到达i之前结束。
  由于2条件中的$dep[i] + w[i]$只与i有关，$dep[u]$只与u有关，我们便有了如下做法:
  存储下以每个节点i作为起点的路径$(u, v)$的$dep[u]$值(这里就是$dep[i]$)，以每个节点i作为终点的路径$(u, v)$的$dep[u]$值。维护一个全局的桶，每当遍历到一个点i时:
  1、处理i的子树
  2、将以i为起点路径的$dep[u]$值加入桶。
  3、统计桶里值=$dep[i] + w[i]$的元素个数，更新$ans[i]$。
  4、将以i为终点路径的$dep[u]$值从桶里删去。
  这里本质上是将桶中+1/-1事件挂在每个点上，每到一个点时查询桶中对应位置的子树和。这个打正负标记求和的思想在线性结构和树结构上都有广泛运用，常常与差分一起出现。
  这里呢?我们发现我们通过这种办法求出来的元素可能并不全在i子树中，也包括了从其他子树出发的向上路径。我们可以在dfs进入i点时，记录一下当前的答案，处理完i子树之后，将现在的答案与刚刚进入i时的答案相减，就得到了真正的答案了。这就是差分思想的一次体现。
  对于向下的路径，我们发现条件变化了。重新考虑原路径。对于原路径$(u, v)$分出的向下路径$(lca, v)$，对i有贡献的条件是:$dep[u] - 2 \times dep[lca] = w[i] - dep[i]$。于是我们也可以仿照上面的做法，先把向下路径反过来变为向上路径，将左边式子的值放入桶里，用右边式子的值查询。但是这个桶可能会有负数下标，要注意一下。
  最后，我们发现对于一条完整的路径，lca可能会被算两次贡献。这在读入路径的时候就判断减掉即可。
  做了一些noip的题目，发现近两年的最难题目都出在树上，而且都与正负标记求和与树上差分联系起来。这一点要着实注意啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
 
using namespace std;
 
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define erep(i, u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define ms(a, b) memset(a, b, sizeof a)
#define SZ(x) (int((x).size()))
#define pb push_back
 
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
    if(flag) x = -x; return x;
}
const int maxn = 300010;
int n, m;
int head[maxn], nxt[maxn << 1], to[maxn << 1], e;
void ae(int x, int y) { to[++e] = y; nxt[e] = head[x]; head[x] = e; }
int fa[maxn][20], dep[maxn], w[maxn];
void dfs1(int u)
{
    rep(i, 1, 19) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    erep(i, u) if(v != fa[u][0])
    {
        fa[v][0] = u; dep[v] = dep[u] + 1;
        dfs1(v);
    }
}
int getlca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    drep(i, 19, 0) if((1 << i) & (dep[u] - dep[v])) u = fa[u][i];
    drep(i, 19, 0) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return u == v ? u : fa[u][0];
}
vector<int> Begin[2][maxn], End[2][maxn];
int cnt[2][maxn * 2], ans[maxn];
void dfs2(int u)
{
    int last = cnt[0][dep[u] + w[u]] + cnt[1][w[u] - dep[u] + n];
    erep(i, u) if(v != fa[u][0]) dfs2(v);
    rep(i, 0, SZ(Begin[0][u]) - 1) ++cnt[0][Begin[0][u][i]];
    rep(i, 0, SZ(Begin[1][u]) - 1) ++cnt[1][Begin[1][u][i] + n];
    ans[u] += cnt[0][dep[u] + w[u]] + cnt[1][w[u] - dep[u] + n] - last;
    rep(i, 0, SZ(End[0][u]) - 1) --cnt[0][End[0][u][i]];
    rep(i, 0, SZ(End[1][u]) - 1) --cnt[1][End[1][u][i] + n];
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
    read(n); read(m); int u, v, lca;
    rep(i, 1, n - 1) read(u), read(v), ae(u, v), ae(v, u);
    rep(i, 1, n) read(w[i]);
    dfs1(1);
    rep(i, 1, m)
    {
        read(u), read(v);
        lca = getlca(u, v);
        if(dep[u] - dep[lca] == w[lca]) --ans[lca];
        Begin[0][u].pb(dep[u]); End[0][lca].pb(dep[u]);
        Begin[1][v].pb(dep[u]- 2 * dep[lca]); End[1][lca].pb(dep[u] - 2 * dep[lca]);
    }
    dfs2(1);
    rep(i, 1, n) printf("%d ", ans[i]); puts("");
    return 0;
}