求助,RE的不明不白

P1600 [NOIP2016 提高组] 天天爱跑步

wucstdio @ 2018-07-18 20:55:20

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node
{
    int dep;
    int parent;
    int w;
    int headu,headv,headlca;
    int ans;
}a[700005];
struct Edge
{
    int to;
    int next;
}e[2000005];
struct Query
{
    int u,v,lca,t;
    int nextu,nextv,nextlca;
}q[700005];
int n,m,edgenum,head[700005],_num[1400005],_numu[1400005],_numv[1400005],_numlca[1400005];
int*num=_num+700000,*numu=_numu+700000,*numv=_numv+700000,*numlca=_numlca+700000;//有可能出现负数
int anc[30][700005],log2[700005];
void add(int u,int v)//加边
{
    e[++edgenum].to=v;
    e[edgenum].next=head[u];
    head[u]=edgenum;
}
void pre()//LCA预处理
{
    for(int i=2;i<=n;i++)
      log2[i]=log2[i>>1]+1;
    for(int i=1;i<=n;i++)
      anc[0][i]=a[i].parent;
    for(int i=1;i<log2[n];i++)
    {
        for(int j=1;j<=n;j++)
          anc[i][j]=anc[i-1][anc[i-1][j]];
    }
}
int LCA(int u,int v)//树上倍增LCA
{
    if(a[u].dep<a[v].dep)swap(u,v);
    for(int i=0;a[u].dep-a[v].dep;i++)
    {
        if((1<<i)&a[u].dep-a[v].dep)
        {
            u=anc[i][u];
        }
    }
    if(u==v)return u;
    for(int i=log2[n];i>=0;i--)
      if(anc[i][u]!=anc[i][v])
        u=anc[i][u],v=anc[i][v];
    return a[u].parent;
}
void dfs(int node)//dfs建树
{
    a[node].dep=a[a[node].parent].dep+1;
    for(int hd=head[node];hd;hd=e[hd].next)
    {
        int to=e[hd].to;
        if(to==a[node].parent)continue;
        a[to].parent=node;
        dfs(to);
    }
}
void work(int node)//深搜计数
{
    int preu=numu[a[node].dep+a[node].w];
    int prev=numv[a[node].dep-a[node].w];
    for(int hd=head[node];hd;hd=e[hd].next)
    {
        int to=e[hd].to;
        if(to==a[node].parent)continue;
        work(to);
    }
    for(int hd=a[node].headu;hd;hd=q[hd].nextu)
        numu[a[node].dep]++;
    for(int hd=a[node].headv;hd;hd=q[hd].nextv)
        numv[a[node].dep-q[hd].t]++;
    a[node].ans+=numu[a[node].dep+a[node].w]-preu;
    a[node].ans+=numv[a[node].dep-a[node].w]-prev;
    for(int hd=a[node].headlca;hd;hd=q[hd].nextlca)
    {
        if(a[q[hd].u].dep==a[node].dep+a[node].w) a[node].ans--;
        numu[a[q[hd].u].dep]--;
        numv[a[q[hd].v].dep-q[hd].t]--;
    }
}
void add2(int i)//用链表把每一个人加到对应的节点上
{
    q[i].nextlca=a[q[i].lca].headlca;
    a[q[i].lca].headlca=i;
    q[i].nextu=a[q[i].u].headu;
    a[q[i].u].headu=i;
    q[i].nextv=a[q[i].v].headv;
    a[q[i].v].headv=i;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i].w);
    pre();
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].u,&q[i].v);
        q[i].lca=LCA(q[i].u,q[i].v);
        q[i].t=a[q[i].u].dep+a[q[i].v].dep-a[q[i].lca].dep*2;
        add2(i);
    }
    work(1);
    for(int i=1;i<=n;i++)
      printf("%d ",a[i].ans);
    printf("\n");
    return 0;
}

|