P1600 [NOIP2016 提高组] 天天爱跑步

//题目大意：有一棵树，在每个节点上会在Pi时刻出现一个观察员，在该时刻观察员如果观察到路过的运动员，那么该观察员的分数加1；
//          现在给定m条路径的起点与终点，每个运动员从0时刻出发，现在询问最终每个观察员的分数
//思路：有画图，看博客
#include<bits/stdc++.h>
using namespace std;
const int M = 3e5 + 11;
int n, m, pat;
int w[M], ans[M], siz[M], dep[M], son[M], f[M], top[M], head[M];
int s[M], t[M], ancestor[M];
int bucket1[M], bucket2[M * 2];
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

};
struct edge {
    int to, next;
    edge(int a = 0, int b = 0) {
        to = a, next = b;
    }
}e[M * 2];//存双边
vector <OPT> opt1[M], opt2[M];//上行链、下行链
void add(int u, int v) {
    e[++pat] = { v,head[u] }, head[u] = pat;
    e[++pat] = { u,head[v] }, head[v] = pat;
}
void dfs(int u, int fa) {//我们这里用树链剖分求lca
    f[u] = fa;
    siz[u] = 1, dep[u] = dep[fa] + 1;
    for (int i = head[u]; i != -1; i = e[i].next) {
        if (e[i].to == fa) continue;
        dfs(e[i].to, u);
        siz[u] += siz[e[i].to];
        if (siz[son[u]] < siz[e[i].to]) son[u] = e[i].to;
    }
}//树链剖分求重儿子
void dfs1(int u, int v) {
    top[u] = v;
    if (son[u]) dfs1(son[u], v);
    for (int i = head[u]; i != -1; i = e[i].next) {
        int q = e[i].to;
        if (q == f[u] || q == son[u]) continue;
        dfs1(q, q);
    }
}//剖分
int LCA(int u, int v) {
    while (top[u] != top[v]) {
        dep[top[u]] >= dep[top[v]] ? u = f[top[u]] : v = f[top[v]];
    }
    return dep[u] <= dep[v] ? u : v;
}

void dfs2(int now) {
    int former = bucket1[dep[now] + w[now]];
    for (int i = head[now]; i != -1; i = e[i].next)
        if (e[i].to != f[now])
            dfs2(e[i].to);
    for (int i = 0; i < opt1[now].size(); i++) bucket1[opt1[now][i].d] += opt1[now][i].tmp;
    int latter = bucket1[dep[now] + w[now]];
    ans[now] += latter - former;
}//所以这里是没有算上LCA的贡献的

void dfs3(int now) {
    int former = bucket2[w[now] - dep[now] + M];//////////这里的桶放越界措施+一个M
    for (int i = head[now]; i!=-1; i = e[i].next) if (e[i].to != f[now]) dfs3(e[i].to);
    for (int i = 0; i < opt2[now].size(); i++) bucket2[opt2[now][i].d + M] += opt2[now][i].tmp;
    int latter = bucket2[w[now] - dep[now] + M];
    ans[now] += latter - former;
}
int main() {
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    for (int i = 1, u, v; i < n; ++i)
        cin >> u >> v, add(u, v);
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= m; i++) cin >> s[i] >> t[i];
    dep[0] = 0, dfs(1, 0), dfs1(1, 1);

    for (int i = 1; i <= m; ++i) {
        ancestor[i] = LCA(s[i], t[i]);
        opt1[s[i]].push_back(OPT(dep[s[i]], 1));
        opt1[ancestor[i]].push_back(OPT(dep[s[i]], -1));
    }
    dfs2(1);

    for (int i = 1; i <= m; i++) {
        int dist = dep[s[i]] + dep[t[i]] - 2 * dep[ancestor[i]];
        opt2[t[i]].push_back(OPT((dist - dep[t[i]]), 1));
        if (f[ancestor[i]]) opt2[f[ancestor[i]]].push_back(OPT((dist - dep[t[i]]), -1));
    }
    dfs3(1);

    for (int i = 1; i < n; i++) printf("%d ", ans[i]);
    printf("%d", ans[n]);
    return 0;
}