给出一棵树和m对起点和终点.第0时刻开始所有的起点会有个人开始向终点跑去.每个时刻可以跑过一条边.
每个节点都会在某个时刻进行一次观测,如果在这个时刻内恰好有人跑到了这个节点,就会被观测到.求每个节点能观测到多少人.

链接

LOJ

COGS

BZOJ

题解

把每个人的移动过程分成两个部分考虑.假设起点是u,终点是v,两个节点的LCA是p.移动过程就可以分为u->LCA和LCA->v两部分.对于第一个部分,假如说路上有人可以观测到该跑步者,则有

dep[u]-dep[i]=w[i]

其中,w[i]是第i个节点的观测时间.做一个变换:

dep[i]+w[i]=dep[u]

问题就转化为了求

\sum_{x \in son[i]}dep[x]=a[i]\ \ 其中 a[i]=dep[i]+w[i]

当且仅当i在u->LCA的路径上时才会观测到跑步者.故可以认为在u->LCA的路径上的每个点放一个权值为dep[u]的物品.然后统计每个节点下权值等于a[i]的物品有多少即为能被观测到的人数.这个问题可以通过树上差分解决.

对于LCA->v的部分,类似的,有

dep[i]-w[i]=2*dep[LCA]-dep[u]

用同样的手法统计答案即可.注意下标可能非负,所以需要进行修正.同时,LCA这个位置的划分需要注意,以避免在该位置观测到同一跑步者两次.

来自三年后的填坑

当初也是同样的思路,只不过是基于树剖和树状数组来统计答案.这次是树上差分版本的.

和当年不同的还有这次记住调cstring了

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 300010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,x,y,p,lsum=1;
int w[N],fa[N],d[N],top[N],head[N],size[N],hson[N],sum[N*2],cnt[N*2],Ans[N];

vector <int> a[N],b[N],c[N],h[N];

struct Edge{
    int t,next;
}e[N*2];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   head[s]=lsum++;
}

inline void Dfs(int x,int f){
    register int i=0;
    size[x]++;
    for (i=head[x];i;i=e[i].next){
        if (e[i].t==f)  continue;
        d[e[i].t]=d[x]+1;   fa[e[i].t]=x;   Dfs(e[i].t,x);
        if (size[e[i].t]>size[hson[x]]) hson[x]=e[i].t;
        size[x]+=size[e[i].t];
    }
}

inline void Cut(int x,int f){
    register int i=0;
    if (!x) return;
    top[hson[x]]=top[x];    Cut(hson[x],x);
    for (i=head[x];i;i=e[i].next){
        if (e[i].t==hson[x]||e[i].t==f) continue;
        top[e[i].t]=e[i].t; Cut(e[i].t,x);
    }
}

inline int LCA(int x,int y){
    while (top[x]^top[y])
        (d[top[x]]>d[top[y]])?x=fa[top[x]]:y=fa[top[y]];
    return (d[x]<d[y])?x:y;
}

inline void Work(int x,int f){
    register int i=0,p=sum[w[x]+d[x]],q=cnt[d[x]-w[x]+n];
    for (i=head[x];i;i=e[i].next){
        if (e[i].t==f)  continue;
        Work(e[i].t,x);
    }
    for (auto j : a[x]) sum[j]++;
    Ans[x]+=sum[w[x]+d[x]]-p;
    for (auto j : b[x]) sum[j]--;
    for (auto j : c[x]) cnt[j]++;
    for (auto j : h[x]) cnt[j]--;
    Ans[x]+=cnt[d[x]-w[x]+n]-q;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();
    for (i=1;i<n;i++){
        x=read();   y=read();
        Add(x,y);   Add(y,x);
    }
    Dfs(1,0);   top[1]=1;   Cut(1,0);
    for (i=1;i<=n;i++)  w[i]=read();
    for (i=1;i<=m;i++){
        x=read();   y=read();
        p=LCA(x,y);
        a[x].push_back(d[x]);   b[p].push_back(d[x]);
        c[y].push_back(2*d[p]-d[x]+n);
        h[p].push_back(2*d[p]-d[x]+n);
    }
    Work(1,0);
    for (i=1;i<=n;i++) printf("%d ",Ans[i]);
    return 0;
}