BZOJ 1782 洛谷 2982 [Usaco2010 Feb]slowdown 慢慢游
2024-08-28 12:31:23
【题解】
一头牛走到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 ;
}
最新文章
- windows下搭建nginx+php+mysql环境
- C++ 局部变量的析构
- Hide a Subpage Using PeopleCode
- Windows 之间用rsync同步数据(cwRsyncServer配置)
- 7第七章联接和APPLY运算符(转载)
- 让DIV垂直居中的几种办法
- stm32之ADC
- python学习笔记之四:条件,循环和其他语句
- ubuntu 下舒畅的使用libreoffice
- 聊天系统Demo,增加Silverlight客户端(附源码)-- ESFramework 4.0 快速上手(09)
- DBUtils-对JDBC简单封装的开源工具类库
- Node.js+Koa开发微信公众号个人笔记(三)响应文本
- spring security oauth2
- 【Monkey】Monkey稳定性测试常用命令
- Pearson 相关系数--最佳理解及相关应用
- vue-router 编程式路由
- Activiti流程设计工具
- PAT 1008 数组元素循环右移问题
- 【x】 PAT/BasicLevel_C++/1002. 写出这个数 (20).cpp
- UVA-10054.The Necklace(欧拉回路)解题报告
热门文章
- linux下的C语言开发 GDB的例子
- IOS程序运行过程
- jQuery:has()和jQuery:contains()及jQuery:empty
- Java调用ssl异常(javax.net.ssl.SSLHandshakeException: No appropriate protocol)
- spring的依赖注入如何降低了耦合
- Geoserver常见问题总结
- hibernate--级联添加
- bash 博弈
- Chromium浏览器编译成功庆祝
- DeepMind:所谓SACX学习范式