TOP

【NOIP2016】天天爱跑步(二)
2017-10-11 14:40:39 】 浏览:10464
Tags:NOIP2016 天天 跑步

i=head[u];i;i=Next[i]) 27 { 28 int v=to[i]; 29 if(v==FA)continue; 30 fa[v][0]=u; 31 dep[v]=dep[u]+1; 32 dfs1(v,u); 33 } 34 } 35 void dfs2(int u,int FA) 36 { 37 int now=dep[u]+w[u],last=Bu[now]; 38 for(int i=head[u];i;i=Next[i]) 39 { 40 int v=to[i]; 41 if(v==FA)continue; 42 dfs2(v,u); 43 } 44 Bu[dep[u]]+=CNT[u]; 45 ans[u]=Bu[now]-last; 46 for(int i=0;i<que1[u].size();i++) Bu[dep[que1[u][i]]]--; 47 } 48 void dfs3(int u,int FA) 49 { 50 int now=dep[u]-w[u],last=Bu[now+eps]; 51 for(int i=head[u];i;i=Next[i]) 52 { 53 int v=to[i]; 54 if(v==FA)continue; 55 dfs3(v,u); 56 } 57 for(int i=0;i<que2[u].size();i++) Bu[que2[u][i]+eps]++; 58 ans[u]+=Bu[now+eps]-last; 59 for(int i=0;i<que3[u].size();i++) Bu[que3[u][i]+eps]--; 60 } 61 int getlca(int x,int y) 62 { 63 if(dep[x]<dep[y])swap(x,y); int Val=dep[x]-dep[y]; 64 for(int j=0;j<=19;j++) if(Val&(1<<j)) x=fa[x][j]; if(x==y)return x; 65 for(int j=19;j>=0;j--) if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; 66 return fa[x][0]; 67 } 68 int main() 69 { 70 //fre("1"); 71 scanf("%d%d",&n,&m); for(int i=1,a,b;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } 72 for(int i=1;i<=n;i++)scanf("%d",&w[i]); 73 dep[1]=1; dfs1(1,0); 74 for(int j=1;j<=19;j++) 75 for(int i=1;i<=n;i++) 76 fa[i][j]=fa[fa[i][j-1]][j-1]; 77 for(int i=1;i<=m;i++) 78 { 79 scanf("%d%d",&S[i],&T[i]); 80 CNT[S[i]]++;//这一个点有多少个起点。 81 LCA[i]=getlca(S[i],T[i]); 82 len[i]=dep[S[i]]+dep[T[i]]-2*dep[LCA[i]]; 83 que1[LCA[i]].push(S[i]); 84 } 85 dfs2(1,0); 86 memset(Bu,0,sizeof Bu); 87 for(int i=1;i<=m;i++) 88 { 89 que2[T[i]].push(dep[T[i]]-len[i]); 90 que3[LCA[i]].push(dep[T[i]]-len[i]); 91 } 92 dfs3(1,0); 93 for(int i=1;i<=m;i++) 94 if(dep[S[i]]-dep[LCA[i]]==w[LCA[i]]) 95 ans[LCA[i]]--; 96 for(int i=1;i<=n;i++) 97 printf("%d ",ans[i]); 98 return 0; 99 } View Code

 


【NOIP2016】天天爱跑步(二) https://www.cppentry.com/bencandy.php?fid=49&id=138263

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇【luogu 1939】【模板】矩阵加速.. 下一篇【原】命令行参数解析及配置编程..