题解： https://xiaoxiaoh.blog.csdn.net/article/details/104280302

一、内容

题目描述

小c 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一一棵包含 nnn 个结点和 n−1n-1n−1 条边的树，每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 111 到 nnn 的连续正整数。

现在有 mmm 个玩家，第 iii 个玩家的起点为 sis_isi​，终点为 tit_iti​。每天打卡任务开始时，所有玩家在第 000 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树，所以每个人的路径是唯一的)

小c 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 jjj 的观察员会选择在第 wjw_jwj​ 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 wjw_jwj​ 秒也理到达了结点 jjj 。小c 想知道每个观察员会观察到多少人?

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一 段时间后再被观察员观察到。 即对于把结点 jjj 作为终点的玩家：若他在第 wjw_jwj​ 秒前到达终点,则在结点 jjj 的观察员不能观察到该玩家；若他正好在第 wjw_jwj​ 秒到达终点,则在结点 jjj 的观察员可以观察到这个玩家。

输入格式

第一行有两个整数 nnn 和 mmm。其中 nnn 代表树的结点数量, 同时也是观察员的数量, mmm 代表玩家的数量。

接下来 n−1n-1n−1 行每行两个整数 uuu 和 vvv，表示结点 uuu 到结点 vvv 有一条边。

接下来一行 nnn 个整数，其中第 jjj 个整数为 wjw_jwj​ , 表示结点 jjj 出现观察员的时间。

接下来 mmm 行，每行两个整数 sis_isi​，和 tit_iti​，表示一个玩家的起点和终点。

对于所有的数据，保证 1≤si,ti≤n,0≤wj≤n1\leq s_i,t_i\leq n, 0\leq w_j\leq n1≤si​,ti​≤n,0≤wj​≤n。
输出格式

输出 111 行 nnn 个整数，第 jjj 个整数表示结点 jjj 的观察员可以观察到多少人。

输入 #1

6 3
2 3
1 2 
1 4 
4 5 
4 6 
0 2 5 1 2 3 
1 5 
1 3 
2 6

输出 #1

2 0 0 1 1 1

二、思路

• 每个玩家的路线由于是一定的，可以拆分为 s —>lca(s, t), lca(s, t)---->t 这2段路径。其中后者不包括lca(s,t)。
• 那么从观察员出发，它在某时刻能观察到人的条件：
  • 点x在第一条路径上: dep[s] - dep[x] = w[x] (x为观察点的节点编号) 由于每秒钟会移动一次，那么代表深度增加或减少。s到x的时间就是 2者的深度之差，只要等于w[x]是观察员出现的时间，那么观察员就可以看到它。
  • 同理点x在第二条路径上： dep[s] + dep[x] - 2 dep[lca] = w[x]。
• 现在以第一条路径出发： 可以转化为 dep[s] = dep[x] + w[x] 。 那么代表s到lca的路径上都增加一个dep[s]的物品， 最终求在这条路径上的x处 dep[x] + w[x]这样的物品数有多少个。
• 那么第二条路径上就是 lca到t的路径上所有点都增加一个 dep[s] - 2 * dep[lca]的物品， 最后求这条路径上x处 w[x] - dep[x] 的物品数有多少。
  
• 2条路径分别求解， 最终所有的人数便是这个点能观察到的人数。

三、代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath> 
using namespace std;
const int N = 3e5 + 5, M = N * 2;
struct E {int v, next;} e[M];
struct Node {
    int ds, st; //ds代表物品类型 st代表增加的个数
    Node(int d, int s): ds(d), st(s){}
}; 
int n, m, u, v, len, lg, ans[N], h[N], w[N], f[N][20], c1[N * 2], c2[N * 2], dep[N];
vector<Node> p1[N], p2[N]; //记录每个点物品的增加与消失
void add(int u, int v) {e[++len].v = v; e[len].next = h[u]; h[u] = len;}
void bfs() {
    lg = int(log(n) / log(2)) + 1;
    queue<int> q; q.push(1); dep[1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int j = h[u]; j; j = e[j].next) {
            int v = e[j].v;
            if (dep[v]) continue;
            dep[v] = dep[u] + 1;
            f[v][0] = u; q.push(v);
            for (int k = 1; k <= lg; k++) f[v][k] = f[f[v][k - 1]][k - 1];
        }
    }
}
int LCA(int x, int y) {
    if (dep[y] > dep[x]) swap(x, y);
    for (int k = lg; k >= 0; k--) {
        if (dep[f[x][k]] >= dep[y]) x = f[x][k];
    }
    if (x == y) return x;
    for (int k = lg; k >= 0; k--) {
        if (f[x][k] != f[y][k]) x = f[x][k], y = f[y][k];
    }
    return f[x][0];
}
void dfs(int u, int fa) {
    int cnt1 = c1[w[u] + dep[u]], cnt2 = c2[w[u] - dep[u] + n];
    for (int j = h[u]; j; j = e[j].next) {
        int v = e[j].v;
        if (v == fa) continue;
        dfs(v, u);
    }
    //把v所有能加的都加上
    for (int i = 0; i < p1[u].size(); i++) {
        Node t = p1[u][i];
        c1[t.ds] += t.st;
    } 
    for (int i = 0; i < p2[u].size(); i++) {
        Node t = p2[u][i];
        c2[t.ds] += t.st;
    } 
    ans[u] = c1[w[u] + dep[u]] - cnt1 + c2[w[u] - dep[u] + n] - cnt2;
} 
int main() {
    scanf("%d%d", &n, &m);  
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        add(u, v); add(v, u);
    }
    bfs();
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]); 
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        int lca = LCA(u, v);
        p1[u].push_back(Node(dep[u], 1)); 
        p1[f[lca][0]].push_back(Node(dep[u], -1));
        p2[v].push_back(Node(dep[u] - 2 * dep[lca] + n, 1)); 
        p2[lca].push_back(Node(dep[u] - 2 * dep[lca] + n, -1)); 
    } 
    dfs(1, 0);
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]); 
    return 0;
}