题解 P1600 【天天爱跑步】

· · 题解

谨以此题解纪念NOIP史上最毒瘤的题

先说一下思路吧

我们发现如果考虑终点和起点的话，需要把这条路径遍历，最优情况下是O(nlogn)的，但题目明确会出现一条链，那么就是O(n^2)的了。

转换一下思想，发现路径分成了两段，一段是向上走，一段是向下走，我们考虑每个观察员的观察特点。

不难发现有两个特点；

1.当观察员在起点到LCA的路径上时，观察员x能观察到的人，当且仅当dep[x] + w[x] = dep[s]时

2.当观察员在LCA到终点的路径上时，能观察到的人，当且仅当dis - dep[t] = w[x] - dep[x] 时。

有了这两个式子，我们就可以做了。 对于两种情况，分别维护一个桶。

一个事实是，点x的贡献一定是一条在经过x的路径所带来的的（观察一下，思考一下）。

所以在计算时，我们要先把递归到这层之前的桶里原来的值记录下来，因为这些是不能算到x的贡献里的，要用后面的减去原来的。

还有，x的贡献是不包含在p子树内的路径的（这些贡献不能算上），所以在处理完一个节点后，我们要把以这个点为LCA的路径在桶里的贡献减去。

还有一点：就是当起点或终点就是LCA时，我们会在上行路和下行路都会计算（重复了），要减去一个。也就是倒数第6行的if语句。 代码如下：（仔细思考一下）

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 300000;
inline int read()
{
    int x = 0 , f = 1;  char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')  f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
vector<int> path[N] , lcafa[N];
int n , m;
int w[N] , s[N] , t[N] , dis[N] , num[N] , dep[N] , fa[N][22] , tong[N] , bact[N << 1] , ans[N];
struct Edge
{
    int to; Edge *nxt;
    Edge(int to = 0,Edge *nxt = NULL) : to(to) , nxt(nxt) {}
}*head[N];
inline void add(int from,int to) {head[from] = new Edge(to,head[from]);}
void get_tree(int now)
{
    for(int i = 1;(1 << i) <= dep[now];i ++)    fa[now][i] = fa[fa[now][i-1]][i-1];
    for(Edge *i = head[now];i;i = i -> nxt)
    {
        int to = i -> to;
        if(dep[to] || to == 1)  continue;
        dep[to] = dep[now] + 1;
        fa[to][0] = now;
        get_tree(to);
    }
}
inline int LCA(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    for(int i = 20;i >= 0;i --) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if(x == y)  return x;
    for(int i = 20;i >= 0;i --)
    {
        if(fa[x][i] == fa[y][i])    continue;
        x = fa[x][i]; y = fa[y][i];
    }
    return fa[x][0];
}
void dfs(int now)
{
    int l = tong[dep[now] + w[now]] , r = bact[w[now] - dep[now] + N];
    for(Edge *i = head[now];i;i = i -> nxt)
    {
        int to = i -> to;
        if(to != fa[now][0]) dfs(to);
    }
    tong[dep[now]] += num[now];
    for(int i = 0;i < path[now].size();i ++)    
    {
        int to = path[now][i];
        bact[dis[to] - dep[t[to]] + N] ++;
    }
    ans[now] += tong[dep[now] + w[now]] - l + bact[w[now] - dep[now] + N] - r;
    for(int i = 0;i < lcafa[now].size();i ++)
    {
        int to = lcafa[now][i];
        tong[dep[s[to]]] --;
        bact[dis[to] - dep[t[to]] + N] --;
    }
}
int main()
{
    n = read(); m = read();
    for(int i = 1 , u , v;i < n;i ++) u = read() , v = read() , add(u,v) , add(v,u);
    dep[1] = 1;
    get_tree(1);
    for(int i = 1;i <= n;i ++)  w[i] = read();
    for(int i = 1 , lca;i <= m;i ++)    
    {
        s[i] = read(); t[i] = read();
        lca = LCA(s[i],t[i]);
        dis[i] = dep[s[i]] + dep[t[i]] - 2 * dep[lca];
        num[s[i]] ++;
        path[t[i]].push_back(i);
        lcafa[lca].push_back(i);
        if(dep[lca] + w[lca] == dep[s[i]])  ans[lca] --;
    }
    dfs(1);
    for(int i = 1;i <= n;i ++)  printf("%d ",ans[i]);
    return 0;
}