题目传送门：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==5){ 2 dep[0]=-1; dfs(1,0); 3 for(int i=1;i<=m;i++){ 4 if(!in[a[i].t]) 5 qx.push(a[i].t); 6 have[a[i].t]++; 7 in[a[i].t]=1; 8 } 9 while(!qx.empty()){ 10 node u=qx.top(); qx.pop(); 11 int x=u.x; 12 if(!in[f[x]]) qx.push(f[x]),in[f[x]]=1; 13 have[f[x]]+=have[x]; 14 } 15 for(int i=1;i<=n;i++) 16 if(w[i]==dep[i]) 17 ans[i]=have[i]; 18 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 19 return 0; 20 }
另一个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 if(op==5){ 2 dep[0]=-1; dfs(1,0); 3 for(int i=1;i<=m;i++){ 4 if(!in[a[i].t]) 5 qx.push(a[i].t); 6 have[a[i].t]++; 7 in[a[i].t]=1; 8 } 9 while(!qx.empty()){ 10 node u=qx.top(); qx.pop(); 11 int x=u.x; 12 if(!in[f[x]]) qx.push(f[x]),in[f[x]]=1; 13 have[f[x]]+=have[x]; 14 } 15 for(int i=1;i<=n;i++) 16 if(w[i]==dep[i]) 17 ans[i]=have[i]; 18 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 19 return 0; 20 }
另一个20分（13,14,15,16号点）：由于Ti=1，假设整棵树根节点为1，不难发现所有观察员能观察到的选手必从其子节点跑来。先对整棵树进行广搜，处理dfs序和一个类似bfs序的东西（数组l和输入r），以及bfs序中选手出现次数的前缀和，其中l[x]表示深度为x的点在bfs序中最早出现的位置，r[x]表示深度为x的点在bfs序中最晚出现的位置。借助这些预处理出的数组，我们就可以通过二分在O(logn)的时间内求出以i为根的字树中深度为dep[i]+w[i]的节点数量，即答案。
1 bool cmpd(int x,int y){ 2 return dfn[x]<=dfn[y]; 3 } 4 bool cmpl(int x,int y){ 5 return low[x]<=low[y]; 6 } 7 if(op==6){ 8 dep[0]=-1; dfs(1,0); t=0; 9 for(int i=1;i<=m;i++) have[a[i].s]++; 10 int last=0,lastdep=-1; q.push(1); 11 while(!q.empty()){ 12 int u=q.front(); q.pop(); 13 num[++t]=u; 14 numsum[t]=numsum[t-1]+have[u]; 15 if(dep[u]!=dep[last]){ 16 r[dep[last]]=t-1; l[dep[u]]=t; 17 lastdep=dep[last]; last=u; 18 } 19 for(int i=head[u];i;i=e[i].next) if(dep[e[i].u]!=lastdep){ 20 q.push(e[i].u); 21 } 22 } 23 for(int i=1;i<=n;i++){ 24 int ceng=dep[i]+w[i]; 25 if(!l[ceng]) continue; 26 int ll=lower_bound(num+l[ceng],num+r[ceng]+1,i,cmpd)-num; 27 int rr=lower_bound(num+l[ceng],num+r[ceng]+1,i,cmpl)-num; 28 if(ll>=rr) continue; 29 ans[i]=numsum[rr-1]-numsum[ll-1]; 30 } 31 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 32 return 0; 33 }
完整的80分组合暴力代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define M 310000 7 #define lowbit(x) (x&(-x)) 8 using namespace std; 9 struct edge{int u,next;}e[M*2]={0}; int head[M]={0},use=0; 10 void Add(int x,int y){use++;e[use].u=y;e[use].next=head[x]; head[x]=use;} 11 struct st{ 12 int s,t; st(){s=t=0;} 13 st(int ss,int tt){s=ss; t=tt;} 14 friend bool operator <(st a,st b){if(a.s==b.s) return a.t<b.t; return a.s<b.s;} 15 }a[M],b[M]; 16 int n,m,w[M]={0},ans[M]={0},la[M]={0},ra[M]={0},lb[M]={0},rb[M]={0}; 17 bool dfs(int x,int fa,int t,int dep){ 18 if(x==t){ 19 if(dep==w[x]) ans[x]++; 20 return 1; 21 } 22 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa){ 23 if(dfs(e[i].u,x,t,dep+1)){ 24 if(dep==w[x]) ans[x]++; 25 return 1; 26 } 27 } 28 return 0; 29 } 30 int dfn[M]={0},low[M]={0},t=0,dep[M]={0}; 31 int p[M]={0},have[M]={0},num[M]={0},numsum[M]={0},l[M]={0},r[M]={0}; 32 void add(int x,int k){ 33 for(int i=x;i<=n;i+=lowbit(i)) p[i]+=k; 34 } 35 int sum(int x){ 36 int k=0; for(int i=x;i;i-=lowbit(i)) k+=p[i]; 37 return k; 38 } 39 int f[M]={0}; 40 void dfs(int x,int fa){ 41 f[x]=fa; 42 dep[x]=dep[fa]+1; dfn[x]=++t; 43 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa) 44 dfs(e[i].u,x); 45 low[x]=t; 46 } 47 queue<int> q; 48 49 bool cmpd(int x,int y){ 50 return dfn[x]<=dfn[y]; 51 } 52 bool cmpl(int x,int y){ 53 return low[x]<=low[y]; 54 } 55 struct node{ 56 int x; node(){x=0;} 57 node(int xx){x=xx;} 58 friend bool operator <(node a,node b){return dep[a.x]<dep[b.x];} 59 }; 60 priority_queue<node> qx; 61 bool in[M]={0}; 62 int main(){ 63 freopen("running.in","r",stdin); 64 freopen("running.out","w",stdout); 65 scanf("%d%d",&n,&m); 66 for(int i=1;i<n;i++){ 67 int x,y; scanf("%d%d",&x,&y); 68 Add(x,y); Add(y,x); 69 } 70 for(int i=1;i<=n;i++) scanf("%d",w+i); 71 for(int i=1;i<=m;i++) scanf("%d%d",&a[i].s,&a[i].t); 72 int op=n%10; 73 if(op<=3||op>=7){ 74 for(int i=1;i<=m;i++) dfs(a[i].s,0,a[i].t,0); 75 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 76 return 0; 77 } 78 if(op==4){ 79 sort(a+1,a+m+1); 80 int na=0,nb=0; 81 for(int i=1;i<=n;i++){ 82 if(a[i].s<=a[i].t) a[++na]=a[i]; 83 else b[++nb]=a[i]; 84 } 85 a[na+1]=st(0,0); 86 for(int i=1;i<=na+1;i++){ 87 if(a[i].s==a[i-1].s) continue; 88 ra[a[i-1].s]=i-1; la[a[i].s]=i; 89 } 90 for(int i=1;i<=nb+1;i++){ 91 if(b[i].s==b[i-1].s) continue; 92 rb[b[i-1].s]=i-1; lb[b[i].s]=i; 93 } 94 for(int i=1;i<=n;i++){ 95 int lid=i-w[i],rid=i+w[i]; 96 if(lid>0&&la[lid]){ 97 int id=lower_bound(a+la[lid],a+ra[lid]+1,st(lid,i))-a; 98 if(id==ra[lid]+1) goto loop; 99 ans[i]+=ra[lid]-id+1; 100 } 101 loop:; 102 if(rid<=n&&lb[rid]){ 103 int id=upper_bound(b+lb[rid],b+rb[rid]+1,st(rid,i))-b; 104 ans[i]+=id-lb[rid]; 105 } 106 } 107 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 108 return 0; 109 } 110 if(op==5){ 111 dep[0]=-1; dfs(1,0); 112 for(int i=1;i<=m;i++){ 113 if(!in[a[i].t]) 114 qx.push(a[i].t); 115 have[a[i].t]++; 116 in[a[i].t]=1; 117 } 118 while(!qx.empty()){ 119 node u=qx.top(); qx.pop(); 120 int x=u.x; 121 if(!in[f[x]]) qx.push(f[x]),in[f[x]]=1; 122 have[f[x]]+=have[x]; 123 } 124 for(int i=1;i<=n;i++) 125 if(w[i]==dep[i]) 126 ans[i]=have[i]; 127 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 128 return 0; 129 } 130 if(op==6){ 131 dep[0]=-1; dfs(1,0); t=0; 132 for(int i=1;i<=m;i++) have[a[i].s]++; 133 int last=0,lastdep=-1; q.push(1); 134 while(!q.empty()){ 135 int u=q.front(); q.pop(); 136 num[++t]=u; 137 numsum[t]=numsum[t-1]+have[u]; 138 if(dep[u]!=dep[last]){ 139 r[dep[last]]=t-1; l[dep[u]]=t; 140 lastdep=dep[last]; last=u; 141 } 142 for(int i=head[u];i;i=e[i].next) if(dep[e[i].u]!=lastdep){ 143 q.push(e[i].u); 144 } 145 } 146 for(int i=1;i<=n;i++){ 147 int ceng=dep[i]+w[i]; 148 if(!l[ceng]) continue; 149 int ll=lower_bound(num+l[ceng],num+r[ceng]+1,i,cmpd)-num; 150 int rr=lower_bound(num+l[ceng],num+r[ceng]+1,i,cmpl)-num; 151 if(ll>=rr) continue; 152 ans[i]=numsum[rr-1]-numsum[ll-1]; 153 } 154 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 155 return 0; 156 } 157 }
其实光Ti=1的情况，就已经称得上NOIP day1 T2了.....
下面说下正解：
题目的数据范围（特别是Ti和Si等于1的情况）是特别有启发作用的。对于一组路径（Si,Ti）,我们可以考虑将它划分为两个询问（Si,lca）和（lca,Ti）,分别进行求和。
考虑从Si到lca（即从下往上的走）的情况，若一组路径能对点x产生贡献，则必然满足dep[x]+w[x]==dep[Si]且dep[x]≤dep[lca]。我们可以考虑维护一个数组cnt，cnt[i]表示dep[v]==i的节点v的数量。对于每个节点x，维护一个数组cnt，且节点v的范围仅限于以x为根的子树。则该部分答案为cnt[dep[x]+w[x]]。cnt向其父节点fa[x]回溯时，减去所有以x为lca的路径对cnt产生的贡献。该过程仅需一遍dfs
考虑lca到Ti（从上往下走）的情况，若能对点x产生贡献，则必然满足dep[x]-w[x]==dep[lca]-dis(Si,lca)。同理开一个数组cnt，cnt[i]表示dep[v]-dis(Si,lca)==i的节点v的数量。其余处理部分与Si到lca相同。
上述两种方法，分别需要n个cnt数组，且单次更新其父节点cnt值所需时间为O(n)，空间复杂度和事件复杂度均为O（n^2）,直接写显然是不行的。我们考虑使用权值线段树去维护cnt数组，同时处理出整棵树后序遍历的dfs序。假设当前需求Si到lca的路径对x的贡献，则贡献为cnt[low[x]][dep[x]+w[x]]-cnt[dfn[x]-1][dep[x]+w[x]]。同理可得lca到Ti对x的贡献。
至此，时间复杂度和空间复杂度均降低至O(n log n)。
PS：该方法需处理很多边界问题，请特别注意！（比如说统计lca处的答案），同时在处理lca到Ti的情况时，cnt[i]的下标可能为负数，需要做一些特殊处理。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #define M 310000 6 using namespace std; 7 struct edge{int u,next;}e[M*2]={0}; int head[M]={0},use=0; 8 void adde(int x,int y){use++;e[use].u=y;e[use].next=head[x]; head[x]=use;} 9 int f[M][20]={0},dep[M]={0}; 10 int w[M]={0},s[M]={0},t[M]={0},lca[M]={0},n,m; 11 int Cnt[M*4]={0},*cnt=&Cnt[M*2],ans[M]={0},Add[M]={0}; 12 vector<int> add[M],del[M],Del[M]; 13 void dfs(int x,int fa){ 14 dep[x]=dep[fa]+1; f[x][0]=fa; 15 for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1]; 16 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa) dfs(e[i].u,x); 17 } 18 int getlca(int x,int y){ 19 if(dep[x]<dep[y]) swap(x,y); int cha=dep[x]-dep[y]; 20 for(int i=19;i>=0;i--) if((1<<i)&cha) x=f[x][i]; 21 for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; 22 if(x!=y) return f[x][0]; return x; 23 } 24 25 struct sgt{int lx,rx,num;}a[M*50]; 26 int root[M]={0},dfn[M]={0},low[M]={0},T=0,nuse=0; 27 int query(int x,int k,int l,int r){ 28 if(!x||k>r) return 0;//注意在向下找深度更深的点时k可能会>r 29 if(l==r) return a[x].num; 30 int mid=(l+r)>>1; 31 if(k<=mid) return query(a[x].lx,k,l,mid); 32 else return query(a[x].rx,k,mid+1,r); 33 } 34 int updata(int x,int k,int l,int r,int zhi){ 35 int nowid=++nuse; 36 a[nowid].lx=a[x].lx; a[nowid].rx=a[x].rx; a[nowid].num=a[x].num; 37 if(l==r) a[nowid].num+=zhi; 38 else{ 39 int mid=(l+r)>>1; 40 if(k<=mid) a[nowid].lx=updata(a[nowid].lx,k,l,mid,zhi); 41 else a[nowid].rx=updata(a[nowid].rx,k,mid+1,r,zhi); 42 } 43 return nowid; 44 } 45 46 void dfs2(int x,int fa){//由lca到t 47 dfn[x]=T; 48 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa){ 49 dfs2(e[i].u,x); 50 } 51 low[x]=++T; root[T]=root[T-1]; 52 int siz=add[x].size(); 53 for(int i=0;i<siz;i++) 54 root[T]=updata(root[T],dep[x]-add[x][i],-n,n,1); 55 siz=del[x].size(); 56 ans[x]+=query(root[T],dep[x]-w[x],-n,n)-query(root[dfn[x]],dep[x]-w[x],-n,n); 57 for(int i=0;i<siz;i++) 58 root[T]=updata(root[T],dep[x]-del[x][i],-n,n,-1); 59 } 60 61 void dfs3(int x,int fa){//由s到lca 62 dfn[x]=T; 63 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa){ 64 dfs3(e[i].u,x); 65 } 66 low[x]=++T; 67 root[T]=updata(root[T-1],dep[x],1,n,Add[x]); 68 int siz=Del[x].size(); 69 for(int i=0;i<siz;i++) 70 root[T]=updata(root[T],dep[x]+Del[x][i],1,n,-1); 71 ans[x]+=query(root[T],dep[x]+w[x],1,n)-query(root[dfn[x]],dep[x]+w[x],1,n); 72 } 73 74 int main(){ 75 freopen("running.in","r",stdin); 76 freopen("running.out","w",stdout); 77 scanf("%d%d",&n,&m); 78 for(int i=1;i<n;i++){ 79 int x,y; scanf("%d%d",&x,&y); 80 adde(x,y); adde(y,x); 81 } 82 dfs(1,0); 83 for(int i=1;i<=n;i++) scanf("%d",w+i); 84 for(int i=1;i<=m;i++){ 85 int s,t,lca; scanf("%d%d",&s,&t); 86 lca=getlca(s,t); 87 add[t].push_back(dep[s]+dep[t]-2*dep[lca]); 88 del[lca].push_back(dep[s]-dep[lca]); 89 Add[s]++; 90 Del[lca].push_back(dep[s]-dep[lca]); 91 //以上这几句话真的累死我了..... 92 } 93 dfs2(1,0); 94 memset(a,0,sizeof(a)); memset(root,0,sizeof(root)); T=0; 95 memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); nuse=0; 96 dfs3(1,0); 97 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 98 }