题目描述

小C同学认为跑步非常有趣，于是决定制作一款叫作《天天爱跑步》的游戏。

《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含 n 个节点和 n-1 条边的树，任意两个节点存在一条路径互相可达。

树上节点的编号是 1~n 之间的连续正整数。

现在有 m 个玩家，第 i 个玩家的起点为 Si，终点为 Ti。

每天打卡任务开始时，所有玩家在第0秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。

因为地图是一棵树，所以每个人的路径是唯一的。

小C想知道游戏的活跃度，所以在每个节点上都放置了一个观察员。

在节点 j 的观察员会选择在第 Wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj 秒也正好到达了节点 j。

小C想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后，该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。

即对于把节点 j 作为终点的玩家：若他在第 Wj 秒前到达终点，则在节点 j 的观察员不能观察到该玩家；若他正好在第 Wj 秒到达终点，则在节点 j 的观察员可以观察到这个玩家。

样例

输入
6 3
2 3
1 2 
1 4 
4 5 
4 6 
0 2 5 1 2 3 
1 5 
1 3 
2 6

输出
2 0 0 1 1 1

算法1

(LCA，树上差分+（乱搞）) $O(mlogn)$

对于100%数据：

u表示起点，v表示终点

对于一条u到v的路径，先讨论LCA!=u&&LCA!=v的情况：

分为u到LCA的路径和LCA到v的路径

对于u到LCA的路径上的点x，当deep[u]-deep[x]=w[x]时，即w[x]+deep[x]=deep[u]时，这条路径对点x有贡献；

观察发现w[x]+deep[x]是定值，所以统计经过x的路径中，deep[u]=w[x]+deep[x]的路径条数。

对于LCA到v的路径上的点x，当deep[u]-2*deep[LCA]+deep[x]=w[x]时，即w[x]-deep[x]=deep[u]-2*deep[lca]时，这条路径对点x有贡献；

观察发现w[x]-deep[x]是定值，所以统计经过x的路径中，deep[u]-2*deep[lca]=w[x]-deep[x]的路径条数；

接下来就是统计路径条数了，用到树上差分

我们统计的起点(终点）一定在点x子树内，所以统计x子树内有多少起点（终点)的值等于所需值

即统计有多少个在点x子树内的起点的deep[u]的值与deep[x]+w[x]相同

有多少终点的deep[u]-2*deep[lca]与w[x]-deep[x]相同

对于一个值，再u、v上加一个表示这个值+1的标记

考虑到x子树内的路径不一定经过x，所以在father[LCA]上加一个标记表示这个值-1

标记用动态数组储存

然后一遍dfs用两个桶分别统计，统计时值统一加上n，因为可能出现负数

记录下dfs到父亲节点时自己（也就是父亲的儿子）所需值的个数，然后统计完子树的值之后再做差计算自己

对于LCA==u||LCA==v的情况归于以上两类计算，特殊处理一下

另外，对于分裂成两条链LCA可能会被统计两遍，最后特殊判断一下，如果被统计了两遍就减去一遍。

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 300009
using namespace std;
int n,m;
vector<int>G[N];
int W[N];
int S[N],T[N],LCA[N];

int father[N],son[N],depth[N];
int heavyson[N],top[N];
int dfs1(int now,int fa){
    father[now]=fa;
    son[now]=1;
    depth[now]=depth[fa]+1;
    for(int i=0;i<G[now].size();++i){
        if(G[now][i]!=fa){
            dfs1(G[now][i],now);
            son[now]+=son[G[now][i]];
            if(son[G[now][i]]>son[heavyson[now]])heavyson[now]=G[now][i];
        }
    }
}

int dfs2(int now,int first){
    top[now]=first;
    if(!heavyson[now])return 0;
    dfs2(heavyson[now],first);
    for(int i=0;i<G[now].size();++i){
        if(G[now][i]!=father[now]&&G[now][i]!=heavyson[now])dfs2(G[now][i],G[now][i]);
    }
}

int swap(int &a,int &b){
    int t=a;a=b;b=t;
}

int lca(int u,int v){
    int tu=top[u],tv=top[v];
    while(tu!=tv){
        if(depth[tu]<depth[tv]){
            swap(tu,tv);swap(u,v);
        }
        u=father[tu];tu=top[u];
    }
    if(depth[u]<depth[v])return u;
    else return v;
}

int cnt[N];
int T1[N+N],T2[N+N];
struct tag{
    int v,siz;
};
vector<tag>tag1[N];
vector<tag>tag2[N];
int dfs(int now,int a,int b){
    for(int i=0;i<tag1[now].size();++i){
        T1[tag1[now][i].v+N]+=tag1[now][i].siz;
    }
    for(int i=0;i<tag2[now].size();++i){
        T2[tag2[now][i].v+N]+=tag2[now][i].siz;
    }

    for(int i=0;i<G[now].size();++i){
        int v=G[now][i];
        if(v==father[now])continue;
        dfs(v,T1[W[v]+depth[v]+N],T2[W[v]-depth[v]+N]);
    }

    cnt[now]+=T1[W[now]+depth[now]+N]+T2[W[now]-depth[now]+N]-a-b;
}

int read(){
    int r=0,k=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return r*k;
}

int main(){
    n=read();m=read();
    for(int i=1;i<=n-1;++i){
        int x=read(),y=read();
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;++i)W[i]=read();
    for(int i=1;i<=m;++i)S[i]=read(),T[i]=read();
    dfs1(1,0),dfs2(1,1);
    for(int i=1;i<=m;++i)LCA[i]=lca(S[i],T[i]);

    for(int i=1;i<=m;++i){
        if(LCA[i]==T[i]){
            tag1[S[i]].push_back((tag){depth[S[i]],1});
            tag1[father[T[i]]].push_back((tag){depth[S[i]],-1});
        }else if(LCA[i]==S[i]){
            tag2[T[i]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],1});
            tag2[father[S[i]]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],-1});
        }else{
            if(W[LCA[i]]+depth[LCA[i]]==depth[S[i]])--cnt[LCA[i]];
            tag1[S[i]].push_back((tag){depth[S[i]],1});
            tag1[father[LCA[i]]].push_back((tag){depth[S[i]],-1});
            tag2[T[i]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],1});
            tag2[father[LCA[i]]].push_back((tag){depth[S[i]]-2*depth[LCA[i]],-1});
        }
    }

    dfs(1,0,0);

    for(int i=1;i<=n;++i)printf("%d ",cnt[i]);

    return 0;
}