NOIP2016 天天爱跑步 题解

题目链接

题目描述：

首先，把每条路径拆成如下两条路径。

1. 从起点到LCA的路径。
2. 从LCA到终点的路径。

对这两条路径分别处理。

首先，处理从起点到LCA的路径。

为了方便，我们把这条路径拆成两条，进行差分：

用从起点到根的路径，减去从LCA到根的路径，得出这条路径的贡献。

现在我们要处理如下路径：

从x点出发，走到根，出发时间为t，贡献为g（1或-1）。

这个操作对点u有贡献，当且仅当满足如下条件：（设sd[x]为x的深度，w[u]表示结点u出现观察员的时间）

1. x在u的子树中。
2. t[x]+(sd[x]-sd[u])=w[u] (即sd[u]+w[u]=sd[x]+t[x])。

所以，开一个数组记录sd[u]+w[u]的出现次数，dfs到u时，用dfs（u）之后的结果-之前的结果，就是u的子树中的x的贡献。（dfs之后比dfs之前仅多包含了u的子树）。

然后，处理从LCA到终点的路径。

同样，拆成两条，进行差分。

我们设从终点为x，起点为根，出发时间为t，贡献为g（1或-1）。

这个操作对点u有贡献，当且仅当满足如下条件：（设sd[x]为x的深度，w[u]表示结点u出现观察员的时间）

1. x在u的子树中。
2. w[u]=sd[u]+t[x] (即w[u]-sd[u]=t[x])。

同样，开一个数组记录w[u]-sd[u]的出现次数，然后用同样的方法dfs处理。（这里下标有负数，可以通过同时加一个值来解决）。

代码：

#include <stdio.h>
#include <string.h>
int fr[300010],ne[600010];
int v[600010],bs=0,mi=0;
int shu[300010],son[300010];
int sd[300010],top[300010];
int fa[300010],W[300010];
int sl1[1500010],sl2[1500010];
int sl3[1500010],sl4[1500010];
int jg[300010],lc[300010];
struct SLb
{
    int he[300010];
    int r[1200010];
    int z[1200010];
    int s;
    SLb(){s=0;}
    void addlb(int a,int b)
    {
        z[s]=b;
        r[s]=he[a];
        he[a]=s;
        s+=1;
        if(b<mi)
            mi=b;
    }
};
SLb lb1,lb2,lb3,lb4;
void addb(int a,int b)
{
    v[bs]=b;
    ne[bs]=fr[a];
    fr[a]=bs;
    bs+=1;
}
void dfs1(int u,int f)
{
    fa[u]=f;
    son[u]=-1;
    shu[u]=1;
    if(f==-1)
        sd[u]=0;
    else
        sd[u]=sd[f]+1;
    int ma=0;
    for(int i=fr[u];i!=-1;i=ne[i])
    {
        int t=v[i];
        if(t!=f)
        {
            dfs1(t,u);
            if(shu[t]>ma)
            {
                ma=shu[t];
                son[u]=t;
            }
            shu[u]+=shu[t];
        }
    }
}
void dfs2(int u,int f,int tp)
{
    top[u]=tp;
    if(son[u]==-1)
        return;
    dfs2(son[u],u,tp);
    for(int i=fr[u];i!=-1;i=ne[i])
    {
        if(v[i]!=f&&v[i]!=son[u])
            dfs2(v[i],u,v[i]);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(sd[top[x]]>sd[top[y]])
            x=fa[top[x]];
        else
            y=fa[top[y]];
    }
    return sd[x]<sd[y]?x:y;
}
void dfs3(int u,int f)
{
    int yq=W[u]-sd[u]+mi;
    int j=(yq<0?0:sl1[yq]);
    for(int i=lb1.he[u];i!=-1;i=lb1.r[i])
        sl1[lb1.z[i]+mi]+=1;
    for(int i=fr[u];i!=-1;i=ne[i])
    {
        if(v[i]!=f)
            dfs3(v[i],u);
    }
    j=(yq<0?0:sl1[yq])-j;
    jg[u]+=j;
}
void dfs4(int u,int f)
{
    int yq=W[u]+sd[u]+mi;
    int j=(yq<0?0:sl2[yq]);
    for(int i=lb2.he[u];i!=-1;i=lb2.r[i])
        sl2[lb2.z[i]+sd[u]+mi]+=1;
    for(int i=fr[u];i!=-1;i=ne[i])
    {
        if(v[i]!=f)
            dfs4(v[i],u);
    }
    j=(yq<0?0:sl2[yq])-j;
    jg[u]+=j;
}
void dfs5(int u,int f)
{
    int yq=W[u]-sd[u]+mi;
    int j=(yq<0?0:sl3[yq]);
    for(int i=lb3.he[u];i!=-1;i=lb3.r[i])
        sl3[lb3.z[i]+mi]+=1;
    for(int i=fr[u];i!=-1;i=ne[i])
    {
        if(v[i]!=f)
            dfs5(v[i],u);
    }
    j=(yq<0?0:sl3[yq])-j;
    jg[u]-=j;
}
void dfs6(int u,int f)
{
    int yq=W[u]+sd[u]+mi;
    int j=(yq<0?0:sl4[yq]);
    for(int i=lb4.he[u];i!=-1;i=lb4.r[i])
        sl4[lb4.z[i]+sd[u]+mi]+=1;
    for(int i=fr[u];i!=-1;i=ne[i])
    {
        if(v[i]!=f)
            dfs6(v[i],u);
    }
    j=(yq<0?0:sl4[yq])-j;
    jg[u]-=j;
}
int main()
{
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        fr[i]=lb1.he[i]=lb2.he[i]=lb3.he[i]=lb4.he[i]=-1;
    for(int i=0;i<N-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        addb(a,b);
        addb(b,a);
    }
    dfs1(1,-1);
    dfs2(1,-1,1);
    for(int i=1;i<=N;i++)
        scanf("%d",&W[i]);
    for(int i=0;i<M;i++)
    {
        int S,T;
        scanf("%d%d",&S,&T);
        lc[i]=lca(S,T);
        lb2.addlb(S,0);
        lb4.addlb(lc[i],sd[S]-sd[lc[i]]);
        lb1.addlb(T,sd[S]-sd[lc[i]]*2);
        lb3.addlb(lc[i],sd[S]-sd[lc[i]]*2);
        if(W[lc[i]]==sd[S]-sd[lc[i]])
            jg[lc[i]]+=1;
    }
    mi=-mi;
    dfs3(1,-1);
    dfs4(1,-1);
    dfs5(1,-1);
    dfs6(1,-1);
    for(int i=1;i<=N;i++)
        printf("%d ",jg[i]);
    return 0;
}