【NOIP2016】bzoj4719 天天爱跑步

本文主要是介绍【NOIP2016】bzoj4719 天天爱跑步，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description 小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。?天天爱跑步?是一个养成类游戏,需要
玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两
个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。现在有个玩家,第个玩家的起点为Si ,终点为Ti
。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去,
跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)小C想知道游戏的活跃度,
所以在每个结点上都放置了一个观察员。在结点的观察员会选择在第Wj秒观察玩家,
一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也理到达了结点J 。小C想知道每个观察员会观察到多少人?注意:
我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一段时间后再被观察员观察到。即对于把结点J作为终点的玩家:
若他在第Wj秒重到达终点,则在结点J的观察员不能观察到该玩家;若他正好在第Wj秒到达终点,则在结点的观察员可以观察到这个玩家。 Input
第一行有两个整数N和M 。其中N代表树的结点数量, 同时也是观察员的数量, M代表玩家的数量。接下来n-1 行每行两个整数U和V
,表示结点U 到结点V 有一条边。接下来一行N 个整数,其中第个整数为Wj , 表示结点出现观察员的时间。接下来
M行,每行两个整数Si和Ti,表示一个玩家的起点和终点。对于所有的数据,保证。 1<=Si,Ti<=N,0<=Wj<=N Output

输出1行N 个整数,第个整数表示结点的观察员可以观察到多少人。

预处理LCA和深度，把一条路径分成先上再下两部分，可以发现上的要满足 $dep[s]-dep[i]=w[i]$ ，即 $dep[s]=dep[i]+w[i]$ 。下的要满足 $dep[i]-(2*dep[lca]-dep[s])=w[i]$ ，即 $2*dep[lca]-dep[s]=dep[i]-w[i]$ 。这样对于一条路径首位打标记【下端+1，上端父亲-1】，然后利用dfs序扫描，分上下两类维护等号左边的值出现的次数，对于每个点在进入和退出分别计算一次就是子树之和。
总复杂度 $O(n+m)$ ，达到了理论下界。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
int fir[300010],ne[600010],to[600010],
q_fir[300010],q_ne[600010],
s[300010],t[300010],lca[300010],dep[300010],
w[300010],fat[300010],
range_l[300010],range_r[300010],
tag_fir[2][300010],tag_ne[2][600010],tag_x[2][600010],tag_k[2][600010],
renew_fir[300010],renew_ne[600010],renew_v[600010],renew_k[600010],
fa[300010],ans[300010],f[300010],cnt[2][900010],
n,m,clo;
/*0:up 1:down*/
void add_edge(int num,int u,int v)
{ne[num]=fir[u];fir[u]=num;to[num]=v;
}
void add_query(int num,int u)
{q_ne[num]=q_fir[u];q_fir[u]=num;
}
void init()
{int i,u,v;n=rd();m=rd();for (i=1;i<n;i++){u=rd();v=rd();add_edge(i*2,u,v);add_edge(i*2+1,v,u);}for (i=1;i<=n;i++)w[i]=rd();for (i=1;i<=m;i++){s[i]=rd();t[i]=rd();add_query(i*2,s[i]);add_query(i*2+1,t[i]);}
}
int find(int u)
{return u==fa[u]?u:fa[u]=find(fa[u]);
}
void dfs1(int u)
{int i,v,x;range_l[u]=++clo;f[clo]=u;fa[u]=u;for (i=fir[u];i;i=ne[i])if (fat[u]!=(v=to[i])){dep[v]=dep[u]+1;fat[v]=u;dfs1(v);fa[v]=u;}range_r[u]=clo;for (i=q_fir[u];i;i=q_ne[i])if (!lca[x=(i>>1)]&&find(v=((i&1)?s[x]:t[x])))lca[x]=fa[v];
}
void solve_lca()
{dep[1]=1;dfs1(1);
}
void add_tag(int lab,int num,int u,int x,int k)
{tag_ne[lab][num]=tag_fir[lab][u];tag_fir[lab][u]=num;tag_x[lab][num]=x;tag_k[lab][num]=k;
}
void mark()
{int i,kk,j;for (i=1;i<=m;i++)if (s[i]!=lca[i]){add_tag(0,i*2,s[i],dep[s[i]],1);add_tag(0,i*2+1,fat[lca[i]],dep[s[i]],-1);if (t[i]!=lca[i]){add_tag(1,i*2,t[i],2*dep[lca[i]]-dep[s[i]],1);add_tag(1,i*2+1,lca[i],2*dep[lca[i]]-dep[s[i]],-1);}}else{add_tag(1,i*2,t[i],2*dep[lca[i]]-dep[s[i]],1);add_tag(1,i*2+1,fat[lca[i]],2*dep[lca[i]]-dep[s[i]],-1);}
}
void add_renew(int num,int u,int v,int k)
{renew_ne[num]=renew_fir[u];renew_fir[u]=num;renew_v[num]=v;renew_k[num]=k;
}
void count()
{int i,j,kk,v;for (i=1;i<=n;i++){add_renew(i*2,range_l[i]-1,i,-1);add_renew(i*2+1,range_r[i],i,1);}for (i=1;i<=n;i++){for (kk=0;kk<2;kk++)for (j=tag_fir[kk][f[i]];j;j=tag_ne[kk][j])cnt[kk][tag_x[kk][j]+n]+=tag_k[kk][j];for (j=renew_fir[i];j;j=renew_ne[j]){ans[v=renew_v[j]]+=cnt[0][dep[v]+w[v]+n]*renew_k[j];ans[v]+=cnt[1][dep[v]-w[v]+n]*renew_k[j];}}printf("%d",ans[1]);for (i=2;i<=n;i++)printf(" %d",ans[i]);
}
int main()
{init();solve_lca();mark();count();
}