CJOJ - P2253 - [NOIP2016] Love running every day
meaning of the title
Given a tree with n nodes, each node has an attribute Wi
There are m people in the tree. Everyone can move one side per second to get from Si to Ti.Find the number of people who reach the ith node in Wi seconds
solution
LCA+Tree Difference Statistics:
_There are many points of violence on this topic, with 80 points.For points n, m < 1000, you can directly enumerate each person's path, Violence Statistical Answer (25 points)
_For a point with Si=1, that means S is the root node, then only depi=Wi nodes can be counted (20 points)
_For a point with Ti=1, for a node with depi depth, a person can reach this point at the time of Wi, indicating that the depth of this person's starting point is depi+Wi, so we can open a bucket: bacx indicates how many nodes have depth x, so when we reach point k, we record bacdepk+Wk at this point, and the increase of bacdepk+Wk after recursion is completed is the answer of K(20 points)
_In the case of a chain, a person either goes left or right on the chain.We only consider the case of going right: for point i, only point i_wi contributes when it is the starting point, so sweep right once:
_1, Open a bucket of bacx to show how many people have not reached the end point yet starting with x
_2, record the answer baci_wi at the current point i
_3, bacS-for those who end at this point
(15 points)
_In general, a person's path can be divided into two parts: going up and going down (that is, Si>LCASi, Ti>Ti):
_For the path to go up, at the i node, depi+wi=depS contributes. With the idea of T as the root node, open a bucket to differentiate statistics
_For a downward path, at the i node, contribution occurs when depi_wi=depT_disS, T_preT. Pre indicates when to reach LCA if the starting point of the path is LCA, and pre=0 if the starting point of the path is natural.
_Then do the same statistics, and at node i, undo the corresponding bac++ of the starting point Sup of the up path and the ending point Tup of the down path, such as Tup being bacdepT_disS and T_preT++, which at the end of the visit undoes the statistics of the other endpoint corresponding to the starting point Sdown of the down path and the ending point Tup of the up path, a bit like a chain-shaped partial pointAlgorithms for
_It is important to note that if the point contributes to the LCA, the contribution value should be -1 because it is counted twice
Complexity
O((n+m)logn)
Code
#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 );
else
if( 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;
}