【NOIP2016】天天爱跑步

CJOJ——P2253 - 【NOIP2016】天天爱跑步

题意

??给定一棵有$n$个节点的树，每个节点有一个属性$W_i$
??树上有$m$个人，每个人要从$S_i$到达$T_i$，每秒可以移动一条边。求在第$W_i$秒到达第$i$个节点的人的数目

解法

LCA+树上差分统计：
这道题的暴力分很多，有80分。对于$n，m≤1000$的点，可以直接枚举每一个人的路径，暴力统计答案（25分）
??对于$S_i=1$的点，那就说明$S$为根节点，那么只有$dep_i=W_i$的节点才可以被统计到（20分）
??对于$T_i=1$的点，对于一个深度为$dep_i$的节点，一个人能在$W_i$的时刻到达该点，说明这个人的起点的深度是$dep_i+W_i$，所以我们可以开一个桶：$bac_x$表示深度为$x$的节点有多少个，那么到达点$k$的时候，我们记录此时的$bac_{dep_k+W_k}$，当递归完成后$bac_{dep_k+W_k}$增加的部分就是$k$的答案，（20分）
对于一条链的情况，一个人在链上要么往左走，要么往右走。我们只考虑往右走的情况：对于点$i$，只有点$i-w_i$为起点时才会产生贡献，那就向右扫一遍：
??1、开一个桶$bac_x$表示到现在以$x$为起点的还没有到终点的人有多少个
2、记录当前点$i$的答案$bac_{i-w_i}$
??3、对于在该点结束的人的$bac_S$–
??（15分）
??对于普遍情况，可以将一个人走的路径分为向上走和向下走两个部分（即：$S_i-->LCA_{S_i，T_i}-->T_i$）：
??对于向上走的路径，在$i$节点，当$dep_i+w_i=dep_S$时才会产生贡献，借用以T为根节点的思想，开一个桶来差分统计就好了
??对于向下走的路径，在$i$节点，当$dep_i-w_i=dep_T-dis_{S，T}-pre_T$时才会产生贡献，$pre$表示若该路径起点为$LCA$,则走到$LCA$时是什么时刻，若该路径起点为自然起点，则$pre=0$
??然后进行同样的统计，到$i$节点时把向上路径的起点$S_{up}$和向下路径的终点$T_{up}$【起点在上面的终点】的对应的$bac++$,例如$T_{up}$就是$bac_{dep_T-dis_{S，T}-pre_T}++$，在访问结束时将向下路径的起点$S_{down}$和向上路径的终点$T_{up}$对应的另一个端点的统计撤销，这个有点类似于链状部分分的算法
??要注意的是，若该点为LCA且该点产生了贡献，贡献值应该-1，因为统计了两次

复杂度

O（$（n+m）logn$）

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Rint register int
#define Lint long long int
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=300010;
const int E=300005;
struct node
{int next,to;
}e[MAXN*2];
int head[MAXN],num;
int ls[MAXN*40],rs[MAXN*40];
int r1[MAXN*2],r2[MAXN*2];
int f[MAXN][20],dep[MAXN];
int siz[MAXN],son[MAXN];
int dfn[MAXN],top[MAXN];
int s[MAXN],t[MAXN];
int w[MAXN],c[MAXN];
int tag[MAXN*40];
int n,m,L,cnt;
int tot;
void add(int u,int v)
{e[++num]=(node){ head[u],v };head[u]=num;
}
void insert(Rint &k,Rint L,Rint R,Rint x)
{if( !k )   k=++tot;if( L==R )   return ;int mid=(L+R)/2;if( x<=mid )   insert( ls[k],L,mid,x );else   insert( rs[k],mid+1,R,x );
}
void update(Rint k,Rint L,Rint R,Rint l,Rint r,Rint w)
{if( !k )   return ;if( L==l && R==r )   { tag[k]+=w;return ; }int mid=(L+R)/2;if( r<=mid )   update( ls[k],L,mid,l,r,w );elseif( l>=mid+1 )   update( rs[k],mid+1,R,l,r,w );else   update( ls[k],L,mid,l,mid,w ),update( rs[k],mid+1,R,mid+1,r,w );
}
int query(Rint k,Rint L,Rint R,Rint x)
{if( !k || L==R )   return tag[k];if( tag[k] ){if( ls[k] )   tag[ls[k]]+=tag[k];if( rs[k] )   tag[rs[k]]+=tag[k];tag[k]=0;}int mid=(L+R)/2;if( x<=mid )   return query( ls[k],L,mid,x );else   return query( rs[k],mid+1,R,x );
}
void init()
{for(int j=1;j<=L;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
}
void Tarjan(int k)
{siz[k]=1;for(int i=head[k],x; i ;i=e[i].next){x=e[i].to;if( x==f[k][0] )   continue ;f[x][0]=k,dep[x]=dep[k]+1;Tarjan( x );siz[k]+=siz[x];if( siz[x]>siz[son[k]] )   son[k]=x;}
}
void dfs(int k)
{dfn[k]=++cnt;if( son[k] )   top[son[k]]=top[k],dfs( son[k] );for(int i=head[k],x; i ;i=e[i].next){x=e[i].to;if( x==f[k][0] || x==son[k] )   continue ;top[x]=x,dfs( x );}insert( r1[dep[k]+w[k]],1,n,dfn[k] );insert( r2[w[k]-dep[k]+E],1,n,dfn[k] );
}
int LCA(int x,int y)
{if( dep[x]<dep[y] )   swap( x,y );int delta=dep[x]-dep[y];for(int i=0;i<=L;i++)if( delta&(1<<i) )   x=f[x][i];for(int i=L;i>=0;i--)if( f[x][i]!=f[y][i] )x=f[x][i],y=f[y][i];if( x==y )   return x;else   return f[x][0];
}
void work(int u,int v)
{int fa=LCA( u,v );int x=u;while( top[u]!=top[fa] ){update( r1[dep[x]],1,n,dfn[top[u]],dfn[u],1 );u=f[top[u]][0];}update( r1[dep[x]],1,n,dfn[fa],dfn[u],1 );while( top[v]!=top[fa] ){update( r2[dep[x]-2*dep[fa]+E],1,n,dfn[top[v]],dfn[v],1 );v=f[top[v]][0];}update( r2[dep[x]-2*dep[fa]+E],1,n,dfn[fa],dfn[v],1 );update( r1[dep[x]],1,n,dfn[fa],dfn[fa],-1 );
}
int main()
{int u,v;scanf("%d%d",&n,&m);L=log(n)/log(2)+1;for(int i=1;i<=n-1;i++){scanf("%d%d",&u,&v);add( u,v ),add( v,u );}for(int i=1;i<=n;i++)   scanf("%d",&w[i]);Tarjan( 1 ),init();top[1]=1,dfs( 1 );for(int i=1;i<=m;i++){scanf("%d%d",&s[i],&t[i]);work( s[i],t[i] );}for(int i=1;i<=n;i++)   c[i]=query( r1[dep[i]+w[i]],1,n,dfn[i] )+query( r2[w[i]-dep[i]+E],1,n,dfn[i] );for(int i=1;i<=n;i++)   printf("%d ",c[i]);printf("\n");return 0;
}