题目传送门：https://www.luogu.org/problemnew/show/P1600
感觉这两天在处理边界问题上有点神志不清......为了从80的暴力变成100，花了整整一个下午+一个晚上的时间(还好最后还是搞了出来)
题目大意：给你一棵树N个点的无根树，有M个人要从Si走到Ti,行走速度为每秒一条边。对于树上任意节点i，求出所有经过该点时行走时间恰好为Wi的路径数量。且这M个人到达终点后下一秒会立即消失。
先来说说暴力，写得妙的话，这题暴力可以拿80分（是不是很良心？？）
这种题目考场上最好还是打暴力
25分（1到5号点）：直接对于所有的任务，模拟从S跑到T，随后直接统计答案即可。
1 bool dfs(int x,int fa,int t,int dep){ 2 if(x==t){ 3 if(dep==w[x]) ans[x]++; 4 return 1; 5 } 6 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa){ 7 if(dfs(e[i].u,x,t,dep+1)){ 8 if(dep==w[x]) ans[x]++; 9 return 1; 10 } 11 } 12 return 0; 13 }
15分（6,7,8号点）：我们可以将这M个人分为两类（Si＞Ti和Si≤Ti），对于一个点i，我们通过二分统计Sj==i-W[i]和Sj==W[i]-i的数量，随后直接输出即可。
1 if(op==4){ 2 sort(a+1,a+m+1); 3 int na=0,nb=0; 4 for(int i=1;i<=n;i++){ 5 if(a[i].s<=a[i].t) a[++na]=a[i]; 6 else b[++nb]=a[i]; 7 } 8 a[na+1]=st(0,0); 9 for(int i=1;i<=na+1;i++){ 10 if(a[i].s==a[i-1].s) continue; 11 ra[a[i-1].s]=i-1; la[a[i].s]=i; 12 } 13 for(int i=1;i<=nb+1;i++){ 14 if(b[i].s==b[i-1].s) continue; 15 rb[b[i-1].s]=i-1; lb[b[i].s]=i; 16 } 17 for(int i=1;i<=n;i++){ 18 int lid=i-w[i],rid=i+w[i]; 19 if(lid>0&&la[lid]){ 20 int id=lower_bound(a+la[lid],a+ra[lid]+1,st(lid,i))-a; 21 if(id==ra[lid]+1) goto loop; 22 ans[i]+=ra[lid]-id+1; 23 } 24 loop:; 25 if(rid<=n&&lb[rid]){ 26 int id=upper_bound(b+lb[rid],b+rb[rid]+1,st(rid,i))-b; 27 ans[i]+=id-lb[rid]; 28 } 29 } 30 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 31 return 0; 32 }
20分（9,10,11,12号点）：考虑Si=1，不妨设整棵树的根为1,随后求出所有点的深度dep[i]。不难发现观察员i能观察到的选手必从其父亲方向跑来。开一个优先队列，以dep[Ti]为关键字，存储所有的Ti，借此维护f数组，f[i]表示从根节点跑来的人中经过点i（包括以i为终点的人）的人的数量。若点i满足w[i]==dep[i]，则ans[i]=f[i],否则ans[i]=0。
1 void dfs(int x,int fa){ 2 f[x]=fa; 3 dep[x]=dep[fa]+1; dfn[x]=++t; 4 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa) 5 dfs(e[i].u,x); 6 low[x]=t; 7 } 8 9 struct node{ 10 int x; node(){x=0;} 11 node(int xx){x=xx;} 12 friend bool operator <(node a,node b){return dep[a.x]<dep[b.x];} 13 }; 14 priority_queue<node> qx; 15 16 int main(){ 17 if(op==5){ 18 dep[0]=-1; dfs(1,0); 19 for(int i=1;i<=m;i++){ 20 if(!in[a[i].t]) 21 qx.push(a[i].t); 22 have[a[i].t]++; 23 in[a[i].t]=1; 24 } 25 while(!qx.empty()){ 26 node u=qx.top(); qx.pop(); 27 int x=u.x; 28 if(!in[f[x]]) qx.push(f[x]),in[f[x]]=1; 29 have[f[x]]+=have[x]; 30 } 31 for(int i=1;i<=n;i++) 32 if(w[i]==dep[i]) 33 ans[i]=have[i]; 34 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 35 return 0; 36 } 37 }
原文：http://www.cnblogs.com/xiefengze1/p/7719690.html
