【题解】

  一头牛走到i,相当于把i点的子树的点权都加1,查询减慢的次数就是查询目的地的点权。

  预处理dfs序,某个点的子树的dfs序是连续的一段。差分后用树状数组维护,变成点修区查。或者直接线段树区修点查。

  

 #include<cstdio>
#include<algorithm>
#define N 200010
#define rg register
using namespace std;
int n,tot,dfn[N],size[N],p[N],t[N],last[N];
struct edge{
int to,pre;
}e[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
inline void add(int x,int y){for(;x<=n;x+=x&-x) t[x]+=y;}
inline int query(int x){
int ret=; for(;x;x-=x&-x) ret+=t[x]; return ret;
}
void dfs(int x){
dfn[x]=++tot; size[x]=;
for(rg int i=last[x],to;i;i=e[i].pre)
if(!dfn[to=e[i].to]) dfs(to),size[x]+=size[to];
}
int main(){
n=read();
for(rg int i=;i<n;i++){
int u=read(),v=read();
e[++tot]=(edge){v,last[u]}; last[u]=tot;
e[++tot]=(edge){u,last[v]}; last[v]=tot;
}
tot=; dfs();
for(rg int i=;i<=n;i++){
int x=read();
printf("%d\n",query(dfn[x]));
add(dfn[x],); add(dfn[x]+size[x],-);
}
return ;
}

最新文章

  1. windows下搭建nginx+php+mysql环境
  2. C++ 局部变量的析构
  3. Hide a Subpage Using PeopleCode
  4. Windows 之间用rsync同步数据(cwRsyncServer配置)
  5. 7第七章联接和APPLY运算符(转载)
  6. 让DIV垂直居中的几种办法
  7. stm32之ADC
  8. python学习笔记之四:条件,循环和其他语句
  9. ubuntu 下舒畅的使用libreoffice
  10. 聊天系统Demo,增加Silverlight客户端(附源码)-- ESFramework 4.0 快速上手(09)
  11. DBUtils-对JDBC简单封装的开源工具类库
  12. Node.js+Koa开发微信公众号个人笔记(三)响应文本
  13. spring security oauth2
  14. 【Monkey】Monkey稳定性测试常用命令
  15. Pearson 相关系数--最佳理解及相关应用
  16. vue-router 编程式路由
  17. Activiti流程设计工具
  18. PAT 1008 数组元素循环右移问题
  19. 【x】 PAT/BasicLevel_C++/1002. 写出这个数 (20).cpp
  20. UVA-10054.The Necklace(欧拉回路)解题报告

热门文章

  1. linux下的C语言开发 GDB的例子
  2. IOS程序运行过程
  3. jQuery:has()和jQuery:contains()及jQuery:empty
  4. Java调用ssl异常(javax.net.ssl.SSLHandshakeException: No appropriate protocol)
  5. spring的依赖注入如何降低了耦合
  6. Geoserver常见问题总结
  7. hibernate--级联添加
  8. bash 博弈
  9. Chromium浏览器编译成功庆祝
  10. DeepMind:所谓SACX学习范式